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?"

Practice

1. What does the term inversion in an array mean?

easy

A. The total number of elements in the array

B. A pair of elements where the first is greater than the second and appears before it

C. A pair of elements where the first is smaller than the second and appears before it

D. The sum of all elements in the array

Solution

1. Step 1: Understand the definition of inversion

   An inversion is when a larger number appears before a smaller number in the array.

2. Step 2: Compare options with definition

   A pair of elements where the first is greater than the second and appears before it matches this definition exactly, others describe different concepts.

3. Final Answer:

   A pair of elements where the first is greater than the second and appears before it -> Option B

4. Quick Check:

   Inversion = larger before smaller [OK]

Hint: Inversion means bigger number comes before smaller one [OK]

Common Mistakes:

• Confusing inversion with sorted order
• Thinking inversion counts equal elements
• Mixing inversion with total pairs

2. Which of the following C code snippets correctly declares a function to count inversions in an array?

easy

A. int countInversions(int arr[], int n);

B. void countInversions(int arr[], int n);

C. int countInversions(int arr, int n[]);

D. int countInversions(int *arr, int n[]);

Solution

1. Step 1: Check function signature correctness

   The function should return an integer count and take an integer array and its size as parameters.

2. Step 2: Analyze each option

   int countInversions(int arr[], int n); correctly uses int return type and parameters as int arr[] and int n. Others have wrong parameter types or return type.

3. Final Answer:

   int countInversions(int arr[], int n); -> Option A

4. Quick Check:

   Correct function signature returns int and takes int array and size [OK]

Hint: Function returns int and takes int array plus size [OK]

Common Mistakes:

• Using void return type instead of int
• Swapping array and size parameter types
• Using pointer syntax incorrectly

3. What is the output of the following C code snippet?

int arr[] = {2, 4, 1, 3, 5};
int n = 5;
int count = 0;
for(int i = 0; i < n-1; i++) {
  for(int j = i+1; j < n; j++) {
    if(arr[i] > arr[j]) count++;
  }
}
printf("%d", count);

medium

A. 5

B. 4

C. 3

D. 2

Solution

1. Step 1: Identify all inversion pairs in the array

   Pairs where first element is greater than second: (2,1), (4,1), (4,3). Total = 3.

2. Step 2: Confirm count variable increments correctly

   Nested loops check all pairs; count increments for each inversion found, total 3.

3. Final Answer:

   3 -> Option C

4. Quick Check:

   Inversions = 3 [OK]

Hint: Count pairs where left element > right element [OK]

Common Mistakes:

• Counting pairs where left < right
• Missing some inversion pairs
• Off-by-one errors in loops

4. The following code is intended to count inversions but has a bug. What is the bug?

int countInversions(int arr[], int n) {
  int count = 0;
  for(int i = 0; i < n; i++) {
    for(int j = i; j < n; j++) {
      if(arr[i] >= arr[j]) count++;
    }
  }
  return count;
}

medium

A. Inner loop should start from j = i + 1, not j = i

B. The count variable should be initialized outside the function

C. The comparison should be arr[i] < arr[j]

D. The function should return void instead of int

Solution

1. Step 1: Analyze loop ranges for counting pairs

   Inner loop starts at j = i, so it compares arr[i] with itself, causing incorrect counting.

2. Step 2: Correct inner loop start index

   Inner loop should start at j = i + 1 to avoid self-comparison.

3. Final Answer:

   Inner loop should start from j = i + 1, not j = i -> Option A

4. Quick Check:

   Start inner loop at i+1 to avoid self-comparison [OK]

Hint: Inner loop must start after outer loop index [OK]

Common Mistakes:

• Starting inner loop at same index as outer
• Wrong comparison operator
• Returning wrong type

5. Given the array {8, 4, 2, 1}, what is the total number of inversions? Also, explain why this number represents the worst case for inversion counting.

hard

A. 4

B. 0

C. 3

D. 6

Solution

1. Step 1: Count all inversion pairs in the array

   Pairs: (8,4), (8,2), (8,1), (4,2), (4,1), (2,1) total 6 inversions.

2. Step 2: Understand why this is worst case

   The array is sorted in descending order, so every pair is inverted, maximum inversions possible for size 4.

3. Final Answer:

   6 -> Option D

4. Quick Check:

   Descending order array has max inversions = n(n-1)/2 [OK]

Hint: Descending order array has max inversions n(n-1)/2 [OK]

Common Mistakes:

• Counting only adjacent inversions
• Forgetting pairs with elements far apart
• Confusing inversion count with array length