TAOCP 5.1.1 Exercise 6

Let \(a_1 a_2 \ldots a_n\) be a permutation of \(\{1,2,\ldots,n\}\).

taocpmathematicsalgorithmsvolume-3hard

Section 5.1.1: Inversions

Exercise 6. ▶ [26] Design an algorithm that computes the inversion table $b_1 b_2 \ldots b_n$ corresponding to a given permutation $a_1 a_2 \ldots a_n$ of ${1, 2, \ldots, n}$, where the running time is essentially proportional to $n \log n$ on typical computers.

Verified: yes
Solve time: 7m22s

Setup

Let (a_1 a_2 \ldots a_n) be a permutation of ({1,2,\ldots,n}). The inversion table (b_1 b_2 \ldots b_n) is defined by
[ b_j = \bigl|{, i \mid i < \operatorname{pos}(j) \text{ and } a_i > j ,}\bigr|, ] where (\operatorname{pos}(j)) is the index with (a_{\operatorname{pos}(j)} = j). Equivalently, when scanning the permutation from left to right, (b_{a_i}) is the number of elements already seen that are larger than (a_i).

Solution

We compute the inversion table in (O(n \log n)) time using a Fenwick tree (Binary Indexed Tree) over the domain ({1,\ldots,n}). The tree maintains the frequencies of the values that have been processed so far.

Algorithm InversionTable

  1. Allocate an array BIT[0..n] initialized to 0.
    (We use 1‑based indexing; BIT[0] is unused.)
  2. Allocate an array b[1..n] to hold the result.
  3. For (i = 1) to (n):
    • Let (v = a_i).
    • Compute count = query(BIT, n) - query(BIT, v).
      (This is the number of elements (> v) already inserted.)
    • Set b[v] = count.
    • Call update(BIT, v, 1) to insert (v) into the tree.
  4. Output b[1], b[2], …, b[n].

The auxiliary procedures are:

  • query(BIT, k): returns (\sum_{j=1}^k \text{BIT}[j]).
    Implementation: sum = 0; while k > 0: sum += BIT[k]; k -= k & -k; return sum.
  • update(BIT, k, delta): adds delta to BIT[k] and propagates.
    Implementation: while k <= n: BIT[k] += delta; k += k & -k.

Invariant. Before the (i)-th iteration of the loop, the Fenwick tree contains exactly the frequencies of the values (a_1, a_2, \ldots, a_{i-1}). Consequently, query(BIT, n) - query(BIT, v) equals the number of those values that are greater than (v), which by definition is (b_v).

Termination. The loop executes exactly (n) iterations. Each iteration performs a constant number of Fenwick tree operations, each of which examines at most (\lceil \log_2 n \rceil) array entries. Hence the algorithm terminates after (O(n \log n)) elementary steps on a typical computer (where bitwise operations and array accesses are (O(1))).

Complexity. Both query and update run in (O(\log n)) time. The total running time is therefore (O(n \log n)).

[ \boxed{ \begin{array}{l} \text{Algorithm InversionTable}(a_1\ldots a_n): \ \quad \text{BIT}[0\ldots n] \gets 0 \ \quad b[1\ldots n] \gets 0 \ \quad \text{for } i = 1 \text{ to } n: \ \qquad v \gets a_i \ \qquad \text{count} \gets \text{query}(\text{BIT}, n) - \text{query}(\text{BIT}, v) \ \qquad b[v] \gets \text{count} \ \qquad \text{update}(\text{BIT}, v, 1) \ \quad \text{return } b[1\ldots n] \ \text{where } \text{query}(\text{BIT}, k) \text{ and } \text{update}(\text{BIT}, k, \delta) \text{ are standard Fenwick tree operations.} \end{array} } ]

Verification

Test on the permutation (3;1;4;2) ((n=4)):

(i) (v=a_i) BIT contents (frequencies) (\text{query}(4)-\text{query}(v)) (b_v)
1 3 ({}) (0-0=0) (b_3=0)
2 1 ({3}) (1-0=1) (b_1=1)
3 4 ({3,1}) (2-2=0) (b_4=0)
4 2 ({3,1,4}) (3-1=2) (b_2=2)

Result: (b_1=1,; b_2=2,; b_3=0,; b_4=0).
Manual check: inversions of (3;1;4;2) are ((3,1),;(3,2),;(4,2)).
(b_1=1) (only 3 > 1), (b_2=2) (3 and 4 > 2), (b_3=0), (b_4=0). Matches exactly.

Edge cases: (n=1) gives (b_1=0); already sorted permutation (1;2;\ldots;n) yields all (b_j=0); reverse sorted (n;n-1;\ldots;1) yields (b_j = n-j). The algorithm handles all correctly.

This completes the proof. ∎