The most well-known algorithm design technique.

Divide the problem into two or more smaller subproblems, solve them recursively, and then combine the solutions to solve the original problem.

General Divide and Conquer Recurrence (Master Theorem)

If a recurrence relation is of the following format—

T(n) = aT(n/b) + f(n) \quad \text{where } f(n) \in \Theta (n^d), d \ge 0

—we can use Master Theorem¹1. The Master Theorem provides an asymptotic bound by comparing the effort required to split/combine the problem (n^d) to the proliferation of subproblems (a). to quickly tell time efficiency.

Master Theorem:

T(n) \in \begin{cases} \Theta(n^d) & \text{if } a < b^d \\ \Theta(n^d \log n) & \text{if } a = b^d \\ \Theta(n^{\log_b a}) & \text{if } a > b^d \end{cases}

Note — This’ll be on the next exam!

Mergesort

Algorithm:

1. Split array (A) in two and make copies of each half in arrays (B and C).
2. Recursively sort arrays B and C
3. Merge sorted arrays.

Splitting is easy, but how to you merge?

We only need to compare two elements when merging, because B and C are sorted. We keep pointers to the front of B and C, copy the smaller one to A, and advance the pointer.

ALGORITHM Mergesort(A[0..n-1])
    // Sorts array A by recursive mergesort
    // Input: An array A[0..n-1] of orderable elements
    // Output: Array A[0..n-1] sorted in nondecreasing order
    if n \gt 1
        copy A[0..\lfloor n/2\rfloor-1] to B[0..\lfloor n/2\rfloor-1]
        copy A[\lfloor n/2\rfloor..n-1] to C[0..\lceil n/2\rceil-1]
        Mergesort(B[0..\lfloor n/2\rfloor-1])
        Mergesort(C[0..\lceil n/2\rceil-1])
        Merge(B, C, A)

ALGORITHM Merge(B[0..p-1], C[0..q-1], A[0..p+q-1])
    // Merges two sorted arrays into one sorted array
    // Input: Arrays B and C, both sorted
    // Output: Sorted array A containing elements of B and C
    i \leftarrow 0; j \leftarrow 0; k \leftarrow 0
    while i \lt p and j \lt q do
        if B[i] \le C[j]
            A[k] \leftarrow B[i]; i \leftarrow i \text{$+$} 1
        else
            A[k] \leftarrow C[j]; j \leftarrow j \text{$+$} 1
        k \leftarrow k \text{$+$} 1
    if i = p
        copy C[j..q-1] to A[k..p+q-1]
    else
        copy B[i..p-1] to A[k..p+q-1]

Analysis

As a recurrence relation, this is:

T(n) = 2T(n/2) + f(n)

Where f(n) is the merge operation

We know the recursive depth is \log n. In the worst case, we do n comparisons on each level.

Thus, we intuitively know we need at most O(n \log n) comparisons.

Now, let’s return to the master theorem solution.

We can say f(n) \in O(n)

Thus, a=2, b=2, d=1.

Analysis — Thus, T(n) \in \Theta(n \log n) for best, average, and worst cases.

Tradeoff: Extra memory use. Space complexity is O(n).

Quicksort

Select a pivot. Rearrange the list so all element in first s positions are smaller than or equal to the pivot and all the element in the remaining n-s positions are \ge the pivot. Recursively sort the two subarrays.

ALGORITHM Quicksort(A[l..r])
    // Sorts a subarray by quicksort
    // Input: Subarray of array A[0..n-1], defined by indices l and r
    // Output: Subarray A[l..r] sorted in nondecreasing order
    if l \lt r
        s \leftarrow Partition(A[l..r]) // s is a split position
        Quicksort(A[l..s-1])
        Quicksort(A[s+1..r])

Hoare’s Partitioning Algorithm

Maintains two pointers traversing from opposite ends of the array. The left pointer skips elements smaller than the pivot, and the right pointer skips elements larger than the pivot. When both stop, they swap values, and continue until they cross.

ALGORITHM Partition(A[l..r])
    // Partitions a subarray by Hoare's algorithm, using first element as pivot
    // Input: Subarray A[l..r]
    // Output: Partition index s
    p \leftarrow A[l]
    i \leftarrow l; j \leftarrow r \text{$+$} 1
    repeat
        repeat i \leftarrow i \text{$+$} 1 until A[i] \ge p
        repeat j \leftarrow j \text{$-$} 1 until A[j] \le p
        swap(A[i], A[j])
    until i \ge j
    swap(A[i], A[j]) // Undo last swap when pointers cross
    swap(A[l], A[j])
    return j

Analysis

Partitioning can be done in O(n) time, where n is the size of the array.

Let T(n) be the number of comparisons required.

As a recurrence relation, this is:

T(n) = T(n-k) + T(k-1) + n

Note — where the pivot ends up at position k.

To find best/worst/avg we must find the k that causes it.

Worst case, k=1 (our pivot is a max or min). Recurrence becomes T(n) = T(n-1) + n, resulting in O(n^2).

Best case, k=n/2²2. Meaning we partition exactly in half..

This lets us apply master theorem. a=2, b=2, d=1. This is case 2.

T(n) \in \Theta (n \log n )

Average case is more complex to work out, ends up being \Theta(n \log n).

Analysis — Best and average time complexity is \Theta(n \log n). Worst time complexity is O(n^2). Space complexity is O(\log n) for the recursion stack on average.

Improvements

• Pick good pivot (use a median of three).
• Use insertion sort on small subfiles.
• Eliminate recursion.

Note — Using all of these improvements can result in 20—25% improvement.

Binary Tree Algorithms

Structure is obviously ready for divide and conquer.

Height

Computing height of binary tree.

• Idea: Know the height of the left subtree and right subtree, and add 1.

Note — Plus one for the root.

h(T) = \max(h(T_L), h(T_R)) + 1

ALGORITHM Height(T)
    // Computes the height of a binary tree
    // Input: A binary tree T
    // Output: The height of T
    if T = null return -1
    else return max(Height(T.left), Height(T.right)) \text{$+$} 1

Analysis — Time complexity is \Theta(n) because we visit every node once. Space complexity is O(\log n) for balanced trees or O(n) worst-case for recursion.

Closest-Pair by Divide and Conquer

Recall — When we did this by brute force, we generated every single pair and checked the distance (O(n^2)).

Algorithm:

1. Divide points into two subsets, P_1 and P_2 split by a median line x=m.
   • Half of points should be on the left (or on) the line, the other half should be on the right (or on) the line.
2. Find the closest pair in the left half and the closest pair in the right half recursively. Let d = \min(d_1, d_2).
3. We know that the points in-between these pairs are the only points that could possibly be smaller. We check a strip of width 2d centered around the dividing line. For each point in the strip, we only need to check a constant number of points ahead of it (at most 6).

Analysis

This function can be represented as

T(n) = 2T(n/2) + f(n)

The merge phase takes f(n) \in O(n) time if the points are presorted by Y-coordinate.

By master theorem, this gives a=2,b=2,d=1

Analysis — Thus time complexity is \Theta(n \log n). Space complexity is O(n) for holding the points and recursion stack.