Algorithms

NPTEL / GATE CS / UGC NET Core Subject Key Exam Questions: Counting Inversions in an array via modified Merge Sort, Maximum Subarray Sum recurrence, Karatsuba integer multiplication ($O(n^{1.585})$), and Strassen's Matrix Multiplication equations ($T(n) = 7T(n/2) + O(n^2) \implies O(n^{2.81})$).

1. Prerequisites & What You Should Know#

Before mastering Divide and Conquer, ensure familiarity with:

• Recursive function traces: Unwinding the recursion stack and evaluating base cases.
• Master Theorem: Solving recurrences of the form $T(n) = aT(n/b) + f(n)$.
• Subproblem independence: Divide and conquer relies on subproblems being completely disjoint, with no shared memory or overlapping computations.
• Merge step mechanics: Merging two sorted lists in linear $O(n)$ time.

2. Conceptual Intuition: The 3 Canonical Phases#

                          [ Original Problem: Size N ]
                                       |
                     +-----------------+-----------------+
                     |                                   |
                  DIVIDE                              DIVIDE
                     v                                   v
             [ Subproblem N/2 ]                  [ Subproblem N/2 ]
                     |                                   |
                 CONQUER                             CONQUER
               (Recursion)                         (Recursion)
                     v                                   v
             [ Solution N/2 ]                    [ Solution N/2 ]
                     |                                   |
                     +-----------------+-----------------+
                                       |
                                    COMBINE
                                       v
                        [ Final Solution for Size N ]

1. Divide: Partition the problem instance into two or more smaller subproblems of the exact same type.
2. Conquer: Solve the subproblems recursively. When the subproblem size is sufficiently small ($N \le 1$ or base case), solve it directly without recursion.
3. Combine: Merge and synthesize the subproblem solutions into the global solution for the original input.

3. Divide & Conquer vs Dynamic Programming#

4. Benchmark Recurrences in Divide and Conquer#

5. Inversion Count: Measuring Disarray#

An Inversion occurs when two indices $i < j$ have $A[i] > A[j]$.

• Completely sorted array ($[1, 2, 3, 4]$): $0$ inversions.
• Completely reversed array ($[4, 3, 2, 1]$): $\frac{n(n-1)}{2}$ inversions.
• The Core D&C Insight: During the merge step of Merge Sort, if an element $R[j]$ from the right subarray is smaller than $L[i]$ from the left subarray, then because $L$ is already sorted: $\text{Every remaining element from } L[i] \text{ to } L[mid] \text{ is ALSO strictly greater than } R[j]!$ Therefore, we instantly count: $\Delta_{\text{inversions}} = (mid - i + 1)$ without checking them individually! This reduces total runtime from $O(n^2)$ to $O(n \log n)$.

6. Real-World Applications#

1. Fast Fourier Transform (FFT - Cooley-Tukey Algorithm): Decomposes a signal of size $N$ into two signals of size $N/2$ (even and odd indices), reducing polynomial multiplication and audio frequency processing from $O(N^2)$ to $O(N \log N)$. Used in MP3 compression, 5G wireless decoding, and MRI imaging.
2. Computational Geometry (Collision Detection): Fast closest-pair algorithms use divide-and-conquer to prune distant bounding boxes in 3D physics engines and robotics motion planning.
3. Distributed Big Data (MapReduce / Apache Spark): The "Map" phase divides terabytes of input chunks across worker nodes; the "Reduce" phase combines partial results.
4. RSA Cryptography: Fast multiplication of 4096-bit prime integers uses Karatsuba and Toom-Cook divide-and-conquer multiplication.

7. Implementation in C, C++, and Python with Syntax Logic#

#include <stdio.h>
#include <stdlib.h>

/**
 * C Syntax Logic Note:
 * 1. Long long int: Inversion count can reach n(n-1)/2 = ~5 * 10^9 for n=100,000,
 *    which overflows standard 32-bit signed int (max 2.14 * 10^9).
 * 2. Crucial Inversion Formula: If L[i] > R[j], then because the left subarray is
 *    sorted, all remaining elements from i to mid ALSO form inversions with R[j]!
 *    Inversion count addition: inv_count += (mid - i + 1).
 * 3. temp buffer: Passed to avoid re-allocating memory in each recursive frame.
 */

long long mergeAndCount(int arr[], int temp[], int left, int mid, int right) {
    int i = left;    // Index for left subarray
    int j = mid + 1; // Index for right subarray
    int k = left;    // Index for merged output buffer
    long long inv_count = 0;

    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            // Found inversions!
            temp[k++] = arr[j++];
            inv_count += (mid - i + 1); // Key mathematical deduction!
        }
    }

    // Copy remaining elements
    while (i <= mid) temp[k++] = arr[i++];
    while (j <= right) temp[k++] = arr[j++];

    // Copy back to original array
    for (i = left; i <= right; i++) {
        arr[i] = temp[i];
    }
    return inv_count;
}

long long mergeSortAndCount(int arr[], int temp[], int left, int right) {
    long long inv_count = 0;
    if (left < right) {
        int mid = left + (right - left) / 2;

        inv_count += mergeSortAndCount(arr, temp, left, mid);
        inv_count += mergeSortAndCount(arr, temp, mid + 1, right);
        inv_count += mergeAndCount(arr, temp, left, mid, right);
    }
    return inv_count;
}