How do we know INVERSIONS-COUNT algorithm (exercise 14.1-7 from here), implemented in balanced tree really works?

We assume that the tree data structure we're using is an order statistic tree which means that a) it's a balanced binary tree, b) each node $x$ is augmented with $size$ field which tells us the size of the node's subtree (its inner nodes, including $x$).

We also have an array $L[1..n]$ which contains the values of the keys of the tree (not necessarily sorted).

The algorithm uses two helper functions:

RANK(Tree, node_x) - returns the rank of the key of node_x in array $L$.

SEARCH(Tree, L[i]) - returns the node with the same key as the element $L[i]$ in the given array.

This is the code:

Construct an order statistic tree T for all the elements in L
   t = −|L|
   for i from 0 to |L| − 1 do
      t = t + RANK(T, SEARCH(T, L[i]))
      remove the node corresponding to L[i] from T end for
   return t

If the array is sorted then there're no inversions. Therefore t is incremented each time by $1$ because in sorted array each new element is the minimal one and has rank $1$ (because we delete the last node).

If the array is not sorted then why are we guaranteed that the ranks will at some point "overtake" t and produce the correct amount of inversions?

  • 1
    $\begingroup$ Presumably you can prove the correctness of the algorithm by induction. $\endgroup$ Commented Jul 17, 2017 at 7:38
  • $\begingroup$ I believe that RANK returns $i \geq 1$ such that node_x is the $i$th smallest element in the tree. $\endgroup$ Commented Jul 17, 2017 at 11:14

1 Answer 1


At step $i$, the rank of $L[i]$ in $T$ is the number of elements in $L[i],\ldots,L[|L|-1]$ which are at most $L[i]$. Taking into account the $-|L|$ in the beginning, we see that the algorithm counts the number of pairs $i<j$ such that $L[j] \leq L[i]$, which is exactly the number of inversions (assuming all elements are distinct).

  • $\begingroup$ Is the time complexity nlogn even when we already have the tree constructed? $\endgroup$
    – HappyFace
    Commented May 11, 2022 at 10:10
  • $\begingroup$ Searching a tree usually takes logarithmic time. $\endgroup$ Commented May 11, 2022 at 13:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.