Divide and Conquer Algorithms
Open in the Padhaiko app3.1 Binary search, min max finding algorithm
The Divide and Conquer paradigm solves a problem of size in three phases:
- Divide: Partition the problem into smaller independent subproblems of size .
- Conquer: Solve each subproblem recursively (or directly when reaches a small base case).
- Combine: Merge the subproblem solutions into the solution for the original problem.
Its running time typically follows the recurrence , where is the divide cost and is the combine cost.
Binary Search
Binary Search locates a target key in a sorted array by comparing against the middle element () and discarding half of the remaining elements on each comparison.
int binarySearch(int A[], int low, int high, int key) {
while (low <= high) {
int mid = low + (high - low) / 2;
if (A[mid] == key) return mid;
if (key < A[mid]) high = mid - 1;
else low = mid + 1;
}
return -1;
}- Recurrence & Time Complexity: with worst and average case; best case (middle element matches immediately).
- Space Complexity: for iterative binary search; stack space for recursive binary search.
Min-Max Finding Algorithm
A naive linear scan finds both the minimum and maximum of elements using comparisons. Using Divide and Conquer, we split into two halves, recursively find and , and combine with only comparisons: and .
void minMax(int A[], int low, int high, int *mn, int *mx) {
if (low == high) { // 1 element: 0 comparisons
*mn = *mx = A[low];
return;
}
if (high == low + 1) { // 2 elements: 1 comparison
if (A[low] < A[high]) { *mn = A[low]; *mx = A[high]; }
else { *mn = A[high]; *mx = A[low]; }
return;
}
int mid = low + (high - low) / 2;
int mn1, mx1, mn2, mx2;
minMax(A, low, mid, &mn1, &mx1);
minMax(A, mid + 1, high, &mn2, &mx2);
*mn = (mn1 < mn2) ? mn1 : mn2;
*mx = (mx1 > mx2) ? mx1 : mx2;
}Comparison Count of Divide-and-Conquer Min-Max
For (), the number of comparisons satisfies:
Solving yields:
comparisons—a reduction compared to the comparisons of the naive scan (and overall time, recursion stack space).
1
- Trace Binary Search on (indices to ) when searching for
key = 24and when searching forkey = 30. - Compute the exact number of element comparisons made by Divide-and-Conquer Min-Max vs. naive sequential Min-Max on elements.
Tracing Binary Search on :
- Searching
key = 24:- Iteration 1:
low=0, high=7,mid = (0+7)//2 = 3,low = 4. - Iteration 2:
low=4, high=7,mid = (4+7)//2 = 5,high = 4. - Iteration 3:
low=4, high=4,mid = 4, found at index ( probes).
- Iteration 1:
- Searching
key = 30:low=0, high=7,mid=3,low=4.low=4, high=7,mid=5,high=4.low=4, high=4,mid=4,low=5.- Loop terminates (
low=5 > high=4) returns ( probes).
Min-Max comparisons for :
- Divide-and-Conquer: Base comparisons (matching ).
- Naive Sequential: Initializes
min = max = A[0]and performs comparisons for each of the remaining elements: comparisons. - Savings: fewer comparisons.
key = 24is found at index in probes;key = 30returns after probes.- Divide-and-Conquer Min-Max takes comparisons for , saving comparisons over the naive -comparison scan.
3.2 Analysis of sorting algorithms
| Algorithm | Best Case | Average Case | Worst Case | Extra Space | In-Place | Stable |
|---|---|---|---|---|---|---|
| Merge Sort | No | Yes | ||||
| Heap Sort | Yes | No | ||||
| Quick Sort (fixed pivot) | avg / worst | Yes | No | |||
| Randomized Quick Sort | expected | (negligible prob.) | expected | Yes | No |
3.2.1 Merge sort
Merge Sort divides an -element array into two subarrays of size and , recursively sorts both halves, and combines them using the linear-time MERGE procedure.
void merge(int A[], int low, int mid, int high) {
int n1 = mid - low + 1, n2 = high - mid;
int L[n1], R[n2];
for (int i = 0; i < n1; i++) L[i] = A[low + i];
for (int j = 0; j < n2; j++) R[j] = A[mid + 1 + j];
int i = 0, j = 0, k = low;
while (i < n1 && j < n2)
A[k++] = (L[i] <= R[j]) ? L[i++] : R[j++];
while (i < n1) A[k++] = L[i++];
while (j < n2) A[k++] = R[j++];
}
void mergeSort(int A[], int low, int high) {
if (low < high) {
int mid = low + (high - low) / 2;
mergeSort(A, low, mid);
mergeSort(A, mid + 1, high);
merge(A, low, mid, high);
}
}- Recurrence: (Master Theorem Case 2) in all cases (best, average, worst), since splitting and merging always inspect every element.
- Auxiliary Space: for temporary merge arrays and (plus stack frames).
3.2.2 Heap sort
Heap Sort treats the array as an implicit binary max-heap where node has:
and satisfies the max-heap property .
MAX-HEAPIFY(A, n, i): Restores the max-heap property downward from node along a root-to-leaf path in time.BUILD-MAX-HEAP(A, n): CallsMAX-HEAPIFYbottom-up from down to . Because most nodes sit near the bottom with small subtree height , the total cost is linear:
- Sorting Phase: Repeatedly swap the root (maximum) with the last heap element , shrink the heap size to , and call
MAX-HEAPIFY(A, k, 0)for down to .
- Total Time: in all cases; in-place with auxiliary space.
3.2.3 Quick sort
Quick Sort picks a pivot element, calls PARTITION to rearrange in time so elements precede the pivot and elements follow it, and recursively sorts the left and right subarrays (no combine step needed).
int partition(int A[], int low, int high) {
int pivot = A[high], i = low - 1;
for (int j = low; j < high; j++) {
if (A[j] <= pivot) {
i++;
int tmp = A[i]; A[i] = A[j]; A[j] = tmp;
}
}
int tmp = A[i + 1]; A[i + 1] = A[high]; A[high] = tmp;
return i + 1;
}
void quickSort(int A[], int low, int high) {
if (low < high) {
int q = partition(A, low, high);
quickSort(A, low, q - 1);
quickSort(A, q + 1, high);
}
}- Best Case (Balanced Split): .
- Constant-Fraction Split (e.g., ): still resolves to because every full level of the recursion tree costs and the longest path has depth .
- Worst Case (Already Sorted / Reverse Sorted with Endpoint Pivot): Partition produces and elements:
- Average Case: Over all random input permutations, expected time is .
3.2.4 Randomized quick sort
In Randomized Quick Sort, RANDOMIZED-PARTITION selects a pivot index uniformly at random from , swaps with , and then runs standard PARTITION.
- Why Randomize? No fixed input (not even a sorted or reverse-sorted array) can reliably trigger the worst case; performance depends only on the random choices made during execution.
- Expected Running Time Analysis: Let be the sorted elements. Elements and () are compared at most once, and only if the first pivot chosen from the range is either or , which occurs with probability . By linearity of expectation:
Hence Randomized Quick Sort runs in expected time on every input.
2
- Trace Lomuto
PARTITIONon (, pivot ), giving the final array and pivot index . - Trace
BUILD-MAX-HEAPon (-indexed) and state the resulting max-heap array.
Lomuto PARTITION on (pivot ): Initialize . Scan :
- : (skip)
- (): , swap
- (): , swap
- (): skip
- (): , swap
- (): , swap
- (): , swap
- (): skip
- (): , swap
- (): , swap
Finally swap with :
( elements on the left, elements on the right).
BUILD-MAX-HEAP on (): Start from down to :
- (, child ): already .
- (, children ): swap .
- (, children ): swap .
- (, children ): swap , then at idx ( vs child ) swap .
- (, children ): swap , then at idx ( vs ) swap , then at idx ( vs ) swap :
- Final partitioned array: with pivot index .
- Resulting max-heap: .
3.3 Order statistics
The -th order statistic of a set of elements is the -th smallest element (): the minimum is , the maximum is , and the median is (lower median). While sorting finds it in time, selection algorithms find the -th smallest element in time.
3.3.1 Selection in expected linear time
RANDOMIZED-SELECT(A, p, r, i) (Quickselect) adapts Randomized Quick Sort by recursing on only one side of the partition:
int randomizedSelect(int A[], int low, int high, int i) {
if (low == high) return A[low];
int q = randomizedPartition(A, low, high);
int k = q - low + 1; // rank of pivot within A[low..high]
if (i == k) return A[q];
if (i < k) return randomizedSelect(A, low, q - 1, i);
return randomizedSelect(A, q + 1, high, i - k);
}- Expected Time Complexity: On average, the random pivot lands within the middle of elements, shrinking the subproblem to at most :
- Worst-Case Time: If every random pivot happens to be an extreme (min or max), .
3.3.2 Selection in worst case linear time
To guarantee worst-case time, the Median-of-Medians (SELECT) algorithm (Blum, Floyd, Pratt, Rivest, and Tarjan) chooses a guaranteed "good" pivot deterministically:
Median-of-Medians (Worst-Case Linear Selection)
Given an array of elements and target rank :
- Divide the elements into groups of elements (plus at most one leftover group of size ).
- Find the median of each group by insertion sort (constant time per group, total).
- Recursively call
SELECTto find the median of the group medians. - Partition around (let end at rank ). If , return ; otherwise recurse on the left () or right () subarray.
Worst-Case Recurrence Proof: At least half of the groups have medians (excluding 's group and any partial group), and each such group contributes elements . Thus at least elements are , and similarly are . Hence the recursive partition step operates on at most elements:
Since , substitution with proves in the worst case.
3
- Demonstrate the Median-of-Medians (
SELECT) pivot-selection steps on the -element array:
to find the -th smallest element.
- Verify via the substitution method that solves to (for large enough , ignoring floor/ceiling constants).
Median-of-Medians step on (, target ):
- Split into groups of and sort each group:
- Group 1: median
- Group 2: median
- Group 3: median
- Find the median of median-of-medians pivot .
- Partition around :
- Elements : ( elements)
- Pivot sits at rank
- Elements : ( elements).
- Since , recurse on the left -element subarray for rank . Sorting that small subarray gives , whose -th smallest element is .
Substitution proof for : Assume for all . Then:
Choosing ensures , so .
- Median-of-medians selects (rank ), reduces to the elements , and finds the -th smallest element as .
- Choosing in yields .
Exercises
Exercises — Divide and Conquer Algorithms
Derive the closed-form number of element comparisons required by the Divide-and-Conquer Min-Max algorithm when (), and compare its exact comparison count against the naive algorithm for .
Setting up and solving the recurrence: With and , unroll times ():
Comparing at :
- Divide-and-Conquer Min-Max: comparisons.
- Naive sequential scan: comparisons.
; for , Divide-and-Conquer uses comparisons versus for the naive scan.
- Trace
BUILD-MAX-HEAPon (-indexed) and write the resulting max-heap. - Prove why
BUILD-MAX-HEAPruns in time rather than .
Tracing BUILD-MAX-HEAP on (from down to ):
- (, children ): swap .
- (, children ): swap .
- (, children ): swap .
- (, children ): swap , then at idx ( vs ) swap , then at idx ( vs ) swap :
Linear-time proof for BUILD-MAX-HEAP: An -element heap has height and at most nodes at height . Calling MAX-HEAPIFY on a node at height costs , so total work is:
Since every non-leaf is inspected, .
- Resulting max-heap: .
- Summing over heights converges to .
Using a recursion tree, show that even an unbalanced split in Quick Sort, modeled by , still runs in time. Explain how Randomized Quick Sort prevents an adversary from forcing the worst case.
Recursion tree analysis of :
- Level costs .
- Level has nodes and , summing to .
- Every complete level sums to , and once shorter branches terminate at size (first at depth ), remaining levels cost .
- The longest root-to-leaf path follows the factor and reaches size at depth .
Thus total cost across all levels is at most (and from the first full levels), giving .
Role of Randomized Quick Sort: Deterministic Quick Sort using the first or last element degrades to on sorted or reverse-sorted inputs. Randomized Quick Sort chooses the pivot uniformly at random from A[low..high], ensuring that every pair has probability of being compared regardless of input order, yielding expected time on all inputs.
Each level of the recursion tree has cost and maximum depth , yielding . Randomized Quick Sort picks pivots uniformly at random so no fixed input order can trigger the worst case.
Trace Quickselect (SELECT) on to find the -th smallest element (), assuming each call selects the middle element as pivot (or describe how RANDOMIZED-SELECT handles each partition). Also state its expected and worst-case time complexities.
Tracing Quickselect on (, ):
- Call 1 (
low=0, high=6, ): Middle index pivot . Partitioning gives ; pivot is at index , rank . - Rank match: Since , the algorithm immediately returns without further recursion!
(If had been requested, since , it would recurse only on .)
Time complexity of RANDOMIZED-SELECT:
- Expected Case: (each random pivot shrinks the subproblem by a constant fraction on average).
- Worst Case: (if the random pivot repeatedly lands at the minimum or maximum).
Quickselect returns as the -th smallest element. RANDOMIZED-SELECT runs in expected time and worst-case time.
In the worst-case linear-time Median-of-Medians (SELECT) algorithm, explain why dividing the elements into groups of guarantees worst-case time, whereas dividing into groups of fails to guarantee time.
Analyzing group size vs. group size :
- Group size : Half of the medians are , and each contributes elements , guaranteeing at least elements on each side. Hence the partition recursive call has size at most :
Because , each level of the recursion tree decreases by a constant geometric factor , summing to .
- Group size : Half of the medians are , and each contributes elements , guaranteeing at least elements on each side. Thus the partition call can have size up to :
Here : every level of the recursion tree still sums to , giving instead of .
Group size yields with , giving . Group size yields with , which degrades to .