Divide and conquer methods notes — Unit 2

Divide and Conquer (D&C) is an elegant, top-down algorithm design paradigm. It tackles massive, complex problems by breaking them down into smaller, identical, and independent subproblems.

⇒1.1 The Three Steps

Every D&C algorithm strictly follows three distinct phases, usually implemented via recursion:

• 1. Divide: Break the original problem of size $n$ into several smaller subproblems. (e.g., Slice an array exactly in half).
• 2. Conquer: Solve the subproblems recursively. If the subproblem sizes are small enough (the base case), solve them instantly in constant time.
• 3. Combine: Merge the solutions of the subproblems together to form the final solution to the original large problem.

The elegance of D&C is that the mathematical analysis perfectly mirrors the algorithmic steps. The recurrence relation $T(n) = aT(n/b) + f(n)$ explicitly represents the Divide and Combine costs as $f(n)$, and the Conquer cost as $aT(n/b)$.

The classic example of Divide and Conquer applied to searching. It strictly requires the input array to be perfectly sorted.

⇒2.1 The Algorithm

• Divide: Compare the target value ($x$) with the middle element of the array.
• Conquer:
  - If $x$ equals the middle element, return the index.
  - If $x$ is less than the middle element, recursively search the left half of the array.
  - If $x$ is greater, recursively search the right half.
• Combine: Nothing to do. The answer from the subproblem is the final answer.

```c
int binarySearch(int arr[], int l, int r, int x) {
if (r >= l) {
int mid = l + (r - l) / 2;
if (arr[mid] == x) return mid;
if (arr[mid] > x)
return binarySearch(arr, l, mid - 1, x);
return binarySearch(arr, mid + 1, r, x);
}
return -1;
}
```

⇒3.1 Time Complexity Proof

Let $T(n)$ be the time to search an array of size $n$.

In the worst case (the element is not present), the algorithm compares the middle element (taking $\Theta(1)$ time) and then recursively calls itself on an array exactly half the size.

Recurrence: $T(n) = T(n/2) + \Theta(1)$

We can solve this using the Master Theorem:
$a = 1, b = 2, f(n) = 1$.
Watershed function: $n^{\log_2 1} = n^0 = 1$.
Since $f(n)$ and the watershed are both constant ($1$), they are in mathematical equilibrium. This triggers Case 2 of the Master Theorem.

Therefore, $T(n) = \Theta(n^{\log_2 1} \log n) = \Theta(\log n)$.

This logarithmic bound is incredibly powerful. Searching a sorted array of 1 million elements takes a maximum of only 20 comparisons.

Invented by John von Neumann in 1945, Merge Sort is a pure, unadulterated Divide and Conquer sorting algorithm. It guarantees highly efficient worst-case performance.

⇒4.1 The Algorithm

• Divide: Find the midpoint of the array and divide it into two equal halves. Recursively divide until you have $n$ arrays, each containing exactly 1 element. (A 1-element array is mathematically considered sorted).
• Conquer: Sort the subproblems. (Happens automatically via the base case).
• Combine: Take two sorted sub-arrays and merge them into a single, larger sorted array. Repeat this until all sub-arrays are merged back into one massive sorted array.

The entire mathematical weight of Merge Sort rests on the Combine step: the `merge()` function.

How do you merge two already sorted arrays ($L$ and $R$) in linear time?
You use a "Two-Pointer" technique.

1. Place pointer `i` at the start of $L$, pointer `j` at the start of $R$, and pointer `k` at the start of an empty temporary array.
2. Compare $L[i]$ and $R[j]$.
3. Whichever is smaller, copy it into $Temp[k]$.
4. Increment the pointer of the array you just pulled from, and increment `k`.
5. Repeat until one array is completely exhausted.
6. Copy the remaining elements of the other array directly into $Temp$.

Time Complexity: Because every element is copied exactly once, merging an array of size $n/2$ with another of size $n/2$ requires exactly $n$ operations. Thus, the combine step takes $\Theta(n)$ time.

⇒6.1 Time Complexity Proof

The algorithm divides the array into 2 halves, recursively sorts both, and merges them in linear time.

Recurrence: $T(n) = 2T(n/2) + \Theta(n)$

Using the Master Theorem:
$a = 2, b = 2, f(n) = n$.
Watershed: $n^{\log_2 2} = n$.
Comparing $f(n)$ and the watershed: $n$ and $n$ are identical (Case 2).
Therefore, $T(n) = \Theta(n \log n)$.

Because the algorithm blindly halves the array regardless of the data, the Best, Worst, and Average cases are exactly the same: $\Theta(n \log n)$. It provides absolute performance guarantees.

⇒6.2 Space Complexity

Merge Sort is NOT an in-place sorting algorithm. The `merge()` procedure strictly requires a temporary array of size $n$ to hold the sorted elements before copying them back. Therefore, the Space Complexity is $O(n)$. This is its only significant engineering drawback.

Developed by Tony Hoare in 1959. Quick Sort takes the exact opposite approach to Merge Sort. While Merge Sort does all the hard work during the Combine step, Quick Sort does all the hard work during the Divide step, making the Combine step trivial.

⇒7.1 The Algorithm

• Divide (Partitioning): Choose one element from the array to act as the "Pivot". Rearrange the entire array so that EVERY element smaller than the pivot is moved to its left, and EVERY element greater than the pivot is moved to its right. The pivot is now strictly in its final, perfectly sorted physical position.
• Conquer: Recursively apply the exact same partitioning logic to the sub-array on the left of the pivot, and the sub-array on the right.
• Combine: Because the array is sorted in-place via swapping during the partition step, no explicit combine step is required.

The mathematical performance of Quick Sort relies entirely on the efficiency of the partition function (usually Lomuto's or Hoare's scheme).

Lomuto's Scheme (Picking the last element as the pivot):
1. Pivot = `arr[high]`.
2. Maintain a pointer `i` (index of smaller element).
3. Loop pointer `j` from `low` to `high-1`.
4. If `arr[j]` is smaller than the pivot, increment `i` and physically swap `arr[i]` with `arr[j]`.
5. After the loop, swap the pivot `arr[high]` with `arr[i+1]`. The pivot is now locked in place.

Because the partition loops through the array exactly once, its time complexity is strictly linear, $\Theta(n)$. Furthermore, it uses swapping, requiring no extra memory.

Unlike Merge Sort, the mathematical recurrence of Quick Sort is entirely dependent on the data and the choice of the pivot.

⇒9.1 The Best Case

The luckiest scenario occurs if the chosen pivot happens to be the exact median of the array every single time. The array is split into two perfectly equal halves.

Recurrence: $T(n) = 2T(n/2) + \Theta(n)$.
By Master Theorem, Best Case Time = $\Theta(n \log n)$.

⇒9.2 The Worst Case (The Nightmare Scenario)

What if the array is already perfectly sorted, and we pick the last element as the pivot? The pivot is the largest element. All $n-1$ elements are placed on its left. The right sub-array is empty.

The array is NOT split in half. It is split into sizes $n-1$ and $0$.

Recurrence: $T(n) = T(n-1) + T(0) + \Theta(n)$
$T(n) = T(n-1) + n$
Solving via expansion: $n + (n-1) + (n-2) ... + 1 = \frac{n(n+1)}{2}$.
Worst Case Time = $O(n^2)$.

A worst-case of $O(n^2)$ is atrocious. However, with randomized pivot selection, the mathematical probability of hitting the worst case is astronomically low. In average, real-world engineering, Quick Sort out-performs Merge Sort because it operates in-place (no $O(n)$ memory allocation overhead) and its inner loop is highly optimized for CPU caching.

Multiplying two $n \times n$ matrices is a fundamental operation in 3D graphics and deep learning. Let $C = A \times B$.

⇒10.1 The Naive Algorithm

The standard algebraic method computes each element of C by taking the dot product of a row in A and a column in B.

```c
for(i=0; i<n; i++) {
for(j=0; j<n; j++) {
C[i][j] = 0;
for(k=0; k<n; k++) {
C[i][j] += A[i][k] * B[k][j];
}
}
}
```

Due to the three nested loops, the time complexity is strictly $\Theta(n^3)$. For massive datasets, cubic time is devastatingly slow. Engineers searched for decades for a faster way.

We can try to apply the Divide and Conquer paradigm to matrix multiplication by splitting matrices A, B, and C into four smaller $(n/2) \times (n/2)$ sub-matrices (quadrants).

To compute the four quadrants of C, we use algebraic block multiplication:

$C_{11} = A_{11}B_{11} + A_{12}B_{21}$
$C_{12} = A_{11}B_{12} + A_{12}B_{22}$
$C_{21} = A_{21}B_{11} + A_{22}B_{21}$
$C_{22} = A_{21}B_{12} + A_{22}B_{22}$

⇒11.1 The Analysis

Look closely at the equations. To compute the full matrix C, we require exactly 8 recursive multiplications of $(n/2) \times (n/2)$ matrices, and 4 additions of those matrices. Matrix addition takes $\Theta(n^2)$ time.

Recurrence: $T(n) = 8T(n/2) + \Theta(n^2)$

Using the Master Theorem:
$a = 8, b = 2$.
Watershed: $n^{\log_2 8} = n^3$.
Comparing $n^3$ to $n^2$, the watershed dominates (Case 1).
Therefore, $T(n) = \Theta(n^3)$.

The standard Divide and Conquer approach failed. It yielded the exact same cubic complexity as the naive triple loop.

In 1969, Volker Strassen made a profound mathematical breakthrough. He proved that matrix multiplication does not require 8 multiplications.

⇒12.1 The Mathematical Trick

Strassen defined 7 highly complex, counter-intuitive intermediate matrices ($P_1$ through $P_7$) using combinations of additions and subtractions.

For example: $P_1 = A_{11}(B_{12} - B_{22})$.

He then proved that the four quadrants of C could be perfectly reconstructed using only additions and subtractions of these 7 $P$ matrices.
e.g., $C_{11} = P_5 + P_4 - P_2 + P_6$.

⇒12.2 The Analysis

By performing massive algebraic acrobatics, Strassen reduced the number of expensive recursive multiplications from 8 to 7. However, he increased the number of cheap matrix additions to 18.

Recurrence: $T(n) = 7T(n/2) + \Theta(n^2)$

Using the Master Theorem:
$a = 7, b = 2$.
Watershed: $n^{\log_2 7} \approx n^{2.81}$.
Comparing $n^{2.81}$ to $n^2$, the watershed dominates (Case 1).
Therefore, $T(n) = \Theta(n^{2.81})$.

This shattered the assumption that matrix multiplication was bound to $O(n^3)$. While constant factors make Strassen slower for small matrices, for massive deep-learning matrices, $O(n^{2.81})$ is vastly superior.

Consider the problem of finding both the absolute maximum and minimum elements in an array of size $n$.

⇒13.1 Naive Approach

Initialize Max and Min to `arr[0]`. Loop through the array, doing two comparisons per element:
`if (arr[i] > Max) Max = arr[i];`
`else if (arr[i] < Min) Min = arr[i];`
Total comparisons in worst case: $2(n-1)$.

⇒13.2 Divide and Conquer Approach

1. Divide the array into two halves.
2. Recursively find the (Max, Min) of the left half, and the (Max, Min) of the right half.
3. Combine: Compare the Left_Max with Right_Max to find the overall Max. Compare Left_Min with Right_Min to find the overall Min. (Takes exactly 2 comparisons).

Recurrence: $T(n) = 2T(n/2) + 2$ (where $T(n)$ is number of comparisons).

Solving this yields exactly $\frac{3n}{2} - 2$ comparisons. By using Divide and Conquer, we reduced the number of hardware operations by 25%.

Unit 2 requires you to write recursive code and mathematically analyze its recurrence relation.

⇒14.1 University Exam Checklist

• Explain the three steps of the Divide and Conquer paradigm.
• Write the recursive C/pseudocode for Binary Search and mathematically prove its time complexity is $O(\log n)$.
• Write the C/pseudocode for the `merge()` function in Merge Sort. Why does the merge step take linear time?
• Derive the recurrence relation for Merge Sort and solve it using the Master Theorem to prove its $O(n \log n)$ complexity.
• Explain the Quick Sort partitioning process (Lomuto or Hoare).
• Analyze the Best Case and Worst Case time complexity of Quick Sort. Why does the worst case occur?
• Explain why the standard Divide and Conquer matrix multiplication fails to improve the $O(n^3)$ boundary.
• How does Strassen's algorithm alter the matrix multiplication recurrence relation? What is the resulting time complexity?
• Derive the total number of comparisons required to find the Maximum and Minimum of an array simultaneously using Divide and Conquer.