# Counting inversion pairs - $n^2$ results in $n \log n$ time?

The number of possible inversions in an array is bounded by $\binom{n}{2}$, i.e $\frac{n(n-1)}{2} \in O(n^2)$. How it is possible to calculate $O(n^2)$ results in $O(n\log n)$ time using something like modified merge sort? (sample algo : http://www.geeksforgeeks.org/counting-inversions/).

• The basic idea is that when the array is partially sorted, you can count multiple inversions with one comparison. – InformedA Dec 12 '14 at 3:57
• Of course. Its a multiple of the remaining items in the first array. Thanks! – basarat Dec 12 '14 at 4:16
• This is very simple. Your prof will often explain this easily for you. – InformedA Dec 12 '14 at 4:21
• Counting and enumerating can be computationally quite different. This of course depends on what you count. Another famous example is counting the number of spanning trees of a graph. This can be done in polynomial time by computing a determinant of a matrix, but of course there might be exponentially many spanning trees. – A.Schulz Dec 12 '14 at 7:20

Swaps that make a permutation are different from the number of inversions. A max of $n*log\, n$ swaps define a permutation. An inversion in a permutation occurs anywhere one element is less than another element at a higher position so a reverse sorted list has $n^2$ inversions but the corresponding permutation has about $\frac{n}{2}$ swaps that define it. We just have to undo the swaps to sort something.
If you are familiar with algebra you might look at the symmetric group for more information on this. Specifically a cycle of length 2 is called a transposition and all permutations can be defined by about $n*log\,n$ transpositions.
• In fact, every permutation is a product of at most $n-1$ transpositions ("swaps"). This has nothing to do with the running time of the divide and conquer algorithm for counting the number of inversions. – Yuval Filmus Dec 12 '14 at 8:03
Here is an even more amazing example. The determinant of an $n\times n$ matrix is a sum of $n!$ products, yet we can compute it in time $O(n^{2.373})$. Here is another striking example. Given a binary string of length $n$, we can count the number of binary strings of the same length in time $O(n)$ even though there are $2^n$ of them. What limits the running time is not the magnitude of the output but its length.
In this particular case, the output length is $O(\log n)$, so it provides no meaningful limit at all. Even though there could be up to $\binom{n}{2}$ many inversions, we can count them without listing them all, just as in the example of binary strings. As you mention, there is an $O(n\log n)$ algorithm doing that. It is conceivable that there is an even faster algorithm, though nothing faster than $O(n)$, since you need (in general) to read at least $n-1$ entries of the permutation before you can be sure what the number of inversions is.