CODEWITHSUNDEEP
algorithm
oski86
oski86

Reputation: 865

Is this algorithm for counting inversions in an array O(n) complex?

I came across a solution in Python for the problem Count inversions in the array, which uses "non-comparative sorting algorithm to get the count". It makes 2 recursive calls to a code which executes bitwise operations.

def inv_count(a, m=(1 << 32)):
    if not m or not a:
        return 0
    count = 0
    ones, zeros = [], []
    for n in a:
        if n & m:
            ones.append(n & ~m)
        else:
            count += len(ones)
            zeros.append(n & ~m)
    m /= 2
    return count + inv_count(ones, m) + inv_count(zeros, m)


print inv_count([1, 2, 3, 4, 5])
print inv_count([2, 4, 1, 3, 5])
print inv_count([5, 4, 3, 2, 1])

Is this solution truly linear O(n)?

Similar SO question claims it's not possible (Is there an algorithm to count array inversions in linear time?), and while there is lot of literature on divide-and-conquer algorithms (with O(n logn) complexity), I would thank for some reference regarding the solution above.

Upvotes: 2

Views: 604

Answers (2)

Dmitriy Kalugin-Balashov
Dmitriy Kalugin-Balashov

Reputation: 343

Yes, It's linear for numbers which are limited by value (32bit).

It's similar with counting sort ( https://en.wikipedia.org/wiki/Counting_sort ) for sorting.

Upvotes: 1

David Eisenstat
David Eisenstat

Reputation: 65468

It's O(n w), where the maximum number is less than 2^w. If w = 32, as the code assumes, then yes, this is a linear-time algorithm. On the other hand, there is an O(n log d)-time comparison-based algorithm for inputs with at most d distinct elements, which is also linear when d = 2^w = 2^32. The Ω(n log n)-time lower bound applies to comparison-based algorithms where all input elements may be distinct.

Upvotes: 3

Related Questions