Count Inversions in Array in DSA C - Time & Space Complexity

Time Complexity: Count Inversions in Array

O(n log n)

Understanding Time Complexity

We want to understand how long it takes to count inversions in an array as the array grows.

The question is: how does the work increase when the array gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

int merge(int arr[], int temp[], int left, int mid, int right) {
    int i = left, j = mid, k = left, inv_count = 0;
    while (i <= mid - 1 && j <= right) {
        if (arr[i] <= arr[j])
            temp[k++] = arr[i++];
        else {
            temp[k++] = arr[j++];
            inv_count += (mid - i);
        }
    }
    while (i <= mid - 1) temp[k++] = arr[i++];
    while (j <= right) temp[k++] = arr[j++];
    for (i = left; i <= right; i++) arr[i] = temp[i];
    return inv_count;
}

int mergeSort(int arr[], int temp[], int left, int right) {
    int mid, inv_count = 0;
    if (right > left) {
        mid = (left + right) / 2;
        inv_count += mergeSort(arr, temp, left, mid);
        inv_count += mergeSort(arr, temp, mid + 1, right);
        inv_count += merge(arr, temp, left, mid + 1, right);
    }
    return inv_count;
}
    

This code counts inversions by using a modified merge sort that counts pairs where a larger number appears before a smaller one.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The merge function compares and merges subarrays while counting inversions.
• How many times: The mergeSort function recursively splits the array and calls merge on each level.

How Execution Grows With Input

As the array size doubles, the number of operations grows a bit more than double but less than square.

Input Size (n)	Approx. Operations
10	About 50 to 70 comparisons and merges
100	About 700 to 900 comparisons and merges
1000	About 10,000 to 15,000 comparisons and merges

Pattern observation: The operations grow roughly proportional to n times log n, meaning it grows faster than linear but much slower than quadratic.

Final Time Complexity

Time Complexity: O(n log n)

This means the time to count inversions grows a bit faster than the size of the array but stays efficient even for large arrays.

Common Mistake

[X] Wrong: "Counting inversions always takes quadratic time because we compare every pair."

[OK] Correct: The merge sort method cleverly counts inversions during merging, avoiding checking every pair directly, so it runs much faster than quadratic time.

Interview Connect

Understanding this method shows you can improve naive solutions by combining sorting and counting cleverly, a skill valuable in many coding challenges.

Self-Check

"What if we used a simple nested loop to count inversions instead of merge sort? How would the time complexity change?"