PadhaikoAll subjects

Divide and Conquer Algorithms

Analysis of Algorithms (ENCT 388)

Open in the Padhaiko app

3.1 Binary search, min max finding algorithm

The Divide and Conquer paradigm solves a problem of size in three phases:

  1. Divide: Partition the problem into smaller independent subproblems of size .
  2. Conquer: Solve each subproblem recursively (or directly when reaches a small base case).
  3. 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.

Recursive and Iterative Binary SearchC
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;
}

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 .

Divide-and-Conquer Min-Max AlgorithmC
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;
}
Theorem

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).

Example 1

1 (6 marks)

  1. Trace Binary Search on (indices to ) when searching for key = 24 and when searching for key = 30.
  2. 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).
  • 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.
Answer:
  1. key = 24 is found at index in probes; key = 30 returns after probes.
  2. Divide-and-Conquer Min-Max takes comparisons for , saving comparisons over the naive -comparison scan.

3.2 Analysis of sorting algorithms

Comparison of Divide-and-Conquer and Heap Sorting Algorithms
AlgorithmBest CaseAverage CaseWorst CaseExtra SpaceIn-PlaceStable
Merge SortNoYes
Heap SortYesNo
Quick Sort (fixed pivot) avg / worstYesNo
Randomized Quick Sort expected (negligible prob.) expectedYesNo

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.

Merge SortC
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);
    }
}

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 .

  1. MAX-HEAPIFY(A, n, i): Restores the max-heap property downward from node along a root-to-leaf path in time.
  2. BUILD-MAX-HEAP(A, n): Calls MAX-HEAPIFY bottom-up from down to . Because most nodes sit near the bottom with small subtree height , the total cost is linear:
  1. 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 .

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).

Lomuto Partition and Quick SortC
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);
    }
}

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.

Hence Randomized Quick Sort runs in expected time on every input.

Example 2

2 (7 marks)

  1. Trace Lomuto PARTITION on (, pivot ), giving the final array and pivot index .
  2. Trace BUILD-MAX-HEAP on (-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 :
Answer:
  1. Final partitioned array: with pivot index .
  2. 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:

Randomized Select (Expected Linear Time)C
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);
}

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:

Definition

Median-of-Medians (Worst-Case Linear Selection)

Given an array of elements and target rank :

  1. Divide the elements into groups of elements (plus at most one leftover group of size ).
  2. Find the median of each group by insertion sort (constant time per group, total).
  3. Recursively call SELECT to find the median of the group medians.
  4. 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.

Example 3

3 (6 marks)

  1. Demonstrate the Median-of-Medians (SELECT) pivot-selection steps on the -element array:

to find the -th smallest element.

  1. Verify via the substitution method that solves to (for large enough , ignoring floor/ceiling constants).

Median-of-Medians step on (, target ):

  1. Split into groups of and sort each group:
    • Group 1: median
    • Group 2: median
    • Group 3: median
  2. Find the median of median-of-medians pivot .
  3. Partition around :
    • Elements : ( elements)
    • Pivot sits at rank
    • Elements : ( elements).
  4. 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 .

Answer:
  1. Median-of-medians selects (rank ), reduces to the elements , and finds the -th smallest element as .
  2. Choosing in yields .

Exercises

Exercises — Divide and Conquer Algorithms

Question 1

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.
Answer:

; for , Divide-and-Conquer uses comparisons versus for the naive scan.

Question 2
  1. Trace BUILD-MAX-HEAP on (-indexed) and write the resulting max-heap.
  2. Prove why BUILD-MAX-HEAP runs 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, .

Answer:
  1. Resulting max-heap: .
  2. Summing over heights converges to .
Question 3

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.

Answer:

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.

Question 4

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).
Answer:

Quickselect returns as the -th smallest element. RANDOMIZED-SELECT runs in expected time and worst-case time.

Question 5

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 .

Answer:

Group size yields with , giving . Group size yields with , which degrades to .

← Iterative and Numeric AlgorithmsGreedy Algorithms →