Complexity of algorithm to find number of elements > element index i in an array

Question

The question is:

Given an array of size N, arr, create another array whose index i = number of elements in sub-array(arr, i+1, N-1) that are greater than arr[i].

Eg. if input array is, 5 3 9 8 2 6 output array is 3 3 0 0 1 0

O(N^2) is simple just two for loops.

I think a O(N*logN) is possible by starting from last element and adding each element to a height-balanced BST with a size element.

Any thoughts on if we can do O(N)?

Answer 1

TL;DR: There is a simple algorithm that runs in time $O(n \log n)$ and finds the inversion vector of a given array. Furthermore, there is a time lower bound of $ \Omega (n \log n) $ for any comparison-based algorithm for this problem, based on a reduction to the sorting problem. I have never read the paper Yuval Filmus referenced to in his answer, but from a brief reading it seems that the operations that the data structure permits are not exactly what you need in order to implement an algorithm for computing the inversion vector.

---

The lower bound:

Edit: As D.W. mentioned, the $ Ω(nlogn) $ lower bound only holds for comparison-based algorithms. There exist sorting algorithms whose running time is $o(nlogn)$, by going outside the comparison-based model.

Suppose by negativity that there exists an algorithm $\mathcal A$ that, given an array of elements $X$ and its length $n$, returns their inversion vector $Y$ in time $o (n\log n)$. Given the assumed algorithm $\mathcal A$, we present a sorting algorithm.

Sorting algorithm:

Input: an array $X$ and its length $n$. In order to simplify the proof, we assume that all of the elements in $X$ are unique, i.e. that no element appears more than once in $X$.

Output: an array that consists of the elements in $X$, in a sorted order.

1. Compute $Y_1 = \mathcal A (X,n)$. Intuitively, $Y_1 [i]$ contains the number of elements in $X$ that are larger than $X[i]$ and "to its right".
2. Generate the array $R = reverse(X)$, i.e. $R[i] = X[n-i]$ for every $i \in [n]$.
3. Compute $Y_2 = \mathcal A (R,n)$. Intuitively, $Y_1 [i]$ contains the number of elements in $R$ that are larger than $R[i]$ and "to its right", i.e. the number of elements in $X$ that are larger than $X[n-i]$ and "to its left".
4. Generate a new array $I$ that satisfies: $I[i] = Y_1 [i] + Y_2 [n-i] + 1$ for every $i\in [n]$. Intuitively, $I[i]$ is the number of elements that are greater than or equal to $X[i]$ in $X$, i.e. the position in which we should put $X[i]$ in the output array.
5. Generate the output array: $O[I[i]] = X[i]$ for every $i\in [n]$.

The correctness of the algorithm is immediate. As to its complexity, steps 2,4 and 5 take $O(n)$, and steps 1 and 3 take $o(n \log n)$. We were therefore able to sort an array in time $o(n\log n)$, which contradicts the known lower bound of $\Omega(n\log n)$ for sorting.

---

An algorithm that runs in time $O(n\log n)$:

1. Create an empty balanced binary search tree, e.g. an AVL tree or a red-black tree. Each node in the tree will hold additional information of the number of elements in its subtree. This data can be easily maintained in insertions and deletions.
2. Go over the input array from right to left, and for each element $X[i]$:
   • Insert $X[i]$ to the tree. While doing so, use the additional information in the nodes in order to compute the number of elements in the tree that are larger than $X[i]$, and save the result in $O[i]$.
   • Finally, update the additional information along the insertion path in the tree and re-balance the tree.
3. Output the array $O$.

The correctness of the algorithm follows from the fact that we insert the elements to the tree from the rightmost element in the array to the leftmost element in the array. Therefore, when inserting the element in the $i$'th position to the tree, the elements that are currently in the tree are all of the elements to its right, and hence the computation in step 2 returns the number of elements in the array that are larger than the $i$'th element and to its right, as desired.

As for the complexity of the algorithm, since the height of the tree is $O(\log n)$, the algorithm runs in time $O(n \log n)$.

Hope that helps :)

Answer 2

Your problem is very related to that of computing the number of inversions in a permutation, or (equivalently) the Kendall tau distance between two permutations; this is the sum of your vector. In fact, your vector (with a very superficial change in the definition) is known as the inversion vector.

There is a classical data structure of Dietz that can be used to compute the inversion vector in time $O(n\log n/\log\log n)$; the $O(n\log n)$ solution you mention is the baseline here. Fredman and Saks proved a matching lower bound showing that the time complexity of Dietz's data structure is optimal. Computing the insertion vector can however be done faster: Chan and Pătraşcu give an $O(n\sqrt{\log n})$ algorithm (see under "Offline dynamic ranking and selection").