CODEWITHSUNDEEP
carraysalgorithm
Raman Singh
Raman Singh

Reputation: 329

Is there an algorithm to count array inversions in linear time?

I know that the number of inversions in an n-element array can be counted in O(n log(n)) operations using an enhanced merge sort.

However, I came across a different solution, which somehow manages to count the number of inversions in O(n) time, provided that the input is a permutation of (1, 2, 3, ..., n−1, n):

EDIT:-

I am sorry for the code I pasted as it doesn't work in all the cases . Actually this code was used for this question and it passed all the cases . But I am still leaving the code so that it may serve as some intuition and maybe a linear time solution for this problem will come up.

NOTE :- The Below Mentioned Code is Incorrect.

/* int in = 0;
    for (int i = 0; i < n; i++) {
        a[i] = a[i] - i - 1;
    }
    for (int i = 0; i < n; i++) {
        if (a[i] > 0)
            in = in + a[i];
        else if (a[i] < -1)
            in = in - a[i] - 1;
    } */

Now the question is can we come up with a linear time solution for this problem ?

Upvotes: 3

Views: 1673

Answers (2)

Alfred Huang
Alfred Huang

Reputation: 18235

The approach is WRONG! Consider the example below!

int a[] = { 2, 3, 1 };

int in = 0;

for (int i = 0; i < n; i++) {
    a[i] = a[i] - i - 1;
}

// a[] = { 1, 1, -2 };

for (int i = 0; i < n; i++) {
    if (a[i] > 0)
        in = in + a[i];
    else if (a[i] < -1)
        in = in - a[i] - 1;
} 

// in = 1 + 1 - (-1) = 3

The correct answer is 2 but it returns 3 here!

Upvotes: 1

Ilmari Karonen
Ilmari Karonen

Reputation: 50338

The obvious answer is that it doesn't. For example, for n = 4 and a = {2, 3, 4, 1}, you code gives the answer 5, even though the correct inversion count is clearly 3.

Upvotes: 3

Related Questions