Divide and Conquer

Divide and Conquer#

Divide and Conquer (D&C) algorithms work by recursively breaking a problem down into two or more sub-problems of the same or related type. This process is repeated until the sub-problems become simple enough to be solved directly.

The D&C process generally involves three steps:

  1. Divide: The problem is divided into one or more smaller sub-problems.

  2. Conquer: The sub-problems are solved recursively. If a sub-problem is small enough, it is solved as a base case.

  3. Combine: The solutions to the sub-problems are combined to produce the solution for the original problem.

We have already encountered a D&C algorithm: Merge Sort.

  • Divide: The array is split into two halves.

  • Conquer: Each half is recursively sorted.

  • Combine: The two sorted halves are merged into a single sorted array.

A significant advantage of D&C algorithms is that their sub-problems are independent, making them easily parallelizable and capable of high performance on multi-core architectures.

Example 1: Max Single-Sell Profit#

Problem: Given an array P of prices for a commodity over a series of time periods, find the day i to buy and a subsequent day j to sell (where j > i) that maximizes the profit P[j] - P[i].

Naive Solution#

A brute-force approach would use nested loops. The outer loop iterates i from 0 to n, and the inner loop iterates j from i to n, tracking the maximum P[j] - P[i] found. This approach has a runtime of \(O(n^2)\).

Divide and Conquer Solution#

We can apply D&C by splitting the array in half. The maximum profit must exist in one of three places:

  1. Entirely in the left half of the array.

  2. Entirely in the right half of the array.

  3. As a “crossing” pair, with the buy day in the left half and the sell day in the right half.

This suggests the following algorithm:

  1. Divide: Split the price array P into left and right halves.

  2. Conquer: Recursively find the max profit for the left half, maxProfit(left), and the right half, maxProfit(right).

  3. Combine: Find the max crossing profit. This is achieved by finding the minimum price in the left half and the maximum price in the right half. The crossing profit is max(right) - min(left). This step requires iterating through both halves, taking \(O(n)\) time.

  4. The final solution is the maximum of these three possibilities: max(maxProfit(left), maxProfit(right), max(right) - min(left)).

Analysis#

  • Base Case: If the array has 0 or 1 element, the profit is 0. \(T(1) = O(1)\).

  • Recursive Step: We make two recursive calls on sub-problems of size \(n/2\), and the combine step (finding the min of the left and max of the right) takes \(O(n)\) time.

  • Recurrence Relation:

    \[T(n) = 2T(\frac{n}{2}) + O(n)\]

  • This recurrence solves to \(O(n \log n)\).

You can see an implementation of this algorithm here.

Example 2: Closest Pair of Points#

Problem: Given a set of \(n\) points in a 2D plane, find the pair of points with the smallest Euclidean distance between them.

Naive Solution#

The naive technique compares every pair of points, calculating the distance for each. This requires \(O(n^2)\) comparisons.

1D Version#

If all points were on a 1D line, we could solve this efficiently by sorting the points (\(O(n \log n)\)) and then scanning the sorted array to compare each point only to its adjacent neighbor (\(O(n)\)). The total time would be \(O(n \log n)\).

However, once sorted, we could also do this in a D&C format, where we split the sorted list into two, find the closest pair in the left and right halves, and then compare those two solutions with the distance between the largest number in the left half and the smallest number in the right half. This gives you a recurrence relation of:

\[T(n) = 2T(\frac{n}{2})+O(1)\]

…which is also \(O(n)\). So, just like the first solution proposed, this is an \(O(n \log n)\) sort followed by an \(O(n)\) scan for the closest pair.

Divide and Conquer Solution (2D)#

We can use a D&C approach to solve the 2D version efficiently.

  1. Setup: Pre-sort the entire set of points based on their x-coordinates. This takes \(O(n \log n)\).

  2. Divide: Find the median x-coordinate and split the set of points into a left half and a right half.

  3. Conquer: Recursively call the algorithm on the left half and the right half. This will return the minimum distance found in each half, \(\delta_L\) and \(\delta_R\) respectively.

  4. Combine:

    • Let \(\delta = \min(\delta_L, \delta_R)\). This is our current best-known minimum distance.

    • The only remaining possibility is a “crossing” pair, where one point is in the left half and one is in the right half, and their distance is less than \(\delta\).

    • We only need to check for points that are within \(\delta\) of the dividing line. We can create a “strip” containing all points within this \(2\delta\)-wide vertical region.

    • We can use a geometric argument to optimize this search. If we sort the points in the strip by their y-coordinate, for any given point \(p\), we only need to check its distance against a constant number of subsequent points in the sorted strip.

    • Geometric Argument: The \(2\delta \times \delta\) box following any point \(p\) can, at most, contain a constant number of points (e.g., 7), because any two points already in the left or right half must be at least \(\delta\) apart.

    • This makes the “combine” step (building the strip and checking pairs) take \(O(n)\) time.

Analysis#

  • Setup Cost: \(O(n \log n)\) to pre-sort by x-coordinate.

  • Recurrence Relation:

    \[T(n) = 2T(\frac{n}{2}) + O(n)\]

  • This recurrence, which represents the D&C part, solves to \(O(n \log n)\).

  • Total Runtime: The \(O(n \log n)\) setup cost and the \(O(n \log n)\) D&C algorithm combine for a total runtime of \(O(n \log n)\).

The actual implementation is not so important, but you can see it here.

Example 3: Quicksort#

Quicksort is a Divide and Conquer sorting algorithm, similar in structure to Mergesort. However, it addresses some of Mergesort’s practical drawbacks:

  • Space: Mergesort requires \(O(n)\) auxiliary space to perform its merging step. Quicksort can be implemented as an in-place sort, requiring only \(O(\log n)\) stack space for recursion.

  • Overhead: The constant factors and function call overhead of Mergesort can make it slower than other sorts on smaller datasets.

  • Adaptivity: Mergesort’s runtime is always \(O(n \log n)\), even if the data is already sorted. Quicksort, while having a worse worst-case, is often faster in practice.

The Quicksort Algorithm#

The key idea of Quicksort is to partition the array not based on position (like Mergesort), but based on value.

Where Mergesort’s steps are:

  • Divide: Trivial (split at the midpoint).

  • Conquer: Recursively sort.

  • Combine: \(O(n)\) merge step.

Quicksort’s steps are:

  • Divide: \(O(n)\) partition step.

  • Conquer: Recursively sort.

  • Combine: Trivial (the array is already sorted in place).

1. The Partition Step#

The partition procedure is the core of the algorithm. It selects an arbitrary element, called the pivot, and rearranges the sub-array in place such that:

  1. All elements to the left of the pivot are less than or equal to it.

  2. All elements to the right of the pivot are greater than or equal to it.

  3. The pivot is placed in its final, sorted position.

A common implementation (Lomuto’s partition scheme) chooses the final element of the array as the pivot. It then runs the following:

pivot = A[-1] # Pivot is the final value of the array
i = 0 # i indicates the edge of the "stuff less than the pivot"
for j in range(len(A)-1):
  if A[j]<pivot: # if A[j] is smaller than pivot
    A[i], A[j] = A[j], A[i] # swap A[i] and A[j]
    i+=1 # increase i
A[i], A[-1] = A[-1], A[i] # swap pivot with first value bigger than the pivot
return i # Return the index of the pivot

2. The Quicksort Algorithm#

With the partition function, the recursive Quicksort algorithm is straightforward:

QUICKSORT(A, start, end)
  if start < end:
    // q is the index of the pivot after partition
    q = PARTITION(A, start, end)
    
    // Recursively sort elements before pivot
    QUICKSORT(A, start, q)
    
    // Recursively sort elements after pivot
    QUICKSORT(A, q+1, end)

A full Python implementation is here.

Runtime Analysis#

The performance of Quicksort depends entirely on the balance of the splits created by the partition function. The partition step itself always takes \(O(n)\) time on a sub-array of size \(n\).

Worst Case#

The worst case occurs when the partition is maximally unbalanced, producing sub-problems of size \(n-1\) and 0. This happens, for example, if the array is already sorted and the last element is chosen as the pivot.

  • Recurrence: \(T(n) = T(n-1) + T(0) + O(n)\)

  • Solution: This expands to an arithmetic series (\(n + (n-1) + ... + 1\)), resulting in a runtime of \(O(n^2)\).

Best Case#

The best case occurs when the partition is perfectly balanced, splitting the array into two sub-problems of size \(\approx n/2\).

  • Recurrence:

\[\begin{split} T(1) =& O(1)\\ T(n) =& 2T(n/2) + O(n) \end{split}\]

  • Solution: This is the same recurrence as Mergesort, which solves to \(O(n \log n)\).

Average Case#

The “average case” assumes all \(n!\) permutations of the input are equally likely. While complex to prove, the average-case runtime is \(O(n \log n)\).

We can gain intuition for this by considering a “bad” split, but one that is not the worst case. For example, if partition consistently produces a 9-to-1 split:

  • Recurrence: \(T(n) = T(9n/10) + T(n/10) + O(n)\)

  • Solution: If we analyze this with a recursion tree, the tree is no longer balanced. The “shallow” side terminates quickly (depth \(\log_{10}(n)\)), while the “deep” side has depth \(\log_{10/9}(n)\).

  • Despite this imbalance, the total work at each level of the tree remains \(O(n)\). Since the maximum depth is \(\log_{10/9}(n) = O(\log n)\), the total runtime is still \(O(n \log n)\).

This demonstrates that as long as the partition is “reasonably good” (i.e., not the absolute worst-case \(n-1\) split every time), Quicksort provides efficient \(O(n \log n)\) performance on average.