Divide and conquer

Why it matters

Divide and conquer is the reasoning behind the fastest general sorting and selection algorithms and many tree algorithms, and it is how you justify a bound like O(n log n) instead of recalling it. Questions in this area check whether you can write the recurrence for your own recursive code, whether you distinguish expected from worst-case time, and whether you can augment a known algorithm (counting during a merge) instead of starting from scratch. The same structure appears in parallel and distributed computation, where independent parts are processed separately and partial results are combined, as in external sorting and map-reduce style aggregation.

Core ideas

Shape and correctness. Split the input into a parts of size about n/b, solve each recursively and combine in f(n) time: T(n) = a T(n/b) + f(n). Correctness is an induction on input size: assume the recursive calls are correct, show the combine step produces a correct result, and check the base cases.

Recursion trees and master-theorem intuition. Level i has a^i subproblems of size n/b^i, so it does a^i f(n/b^i) work. Compare f(n) with n^(log_b a), the number of leaves:

• If f grows polynomially slower, the leaves dominate: T(n) = Θ(n^(log_b a)). Example: 8T(n/2) + n^2 gives Θ(n^3).
• If they match, every level costs about the same and there are about log n levels: Θ(n^(log_b a) log n). Merge sort, 2T(n/2) + n, gives Θ(n log n).
• If f grows polynomially faster (and satisfies a regularity condition), the root dominates: Θ(f(n)). Example: 2T(n/2) + n^2 gives Θ(n^2).

Recurrences that shrink by subtraction rather than by a factor, such as T(n) = T(n-1) + n, are outside the theorem; they sum to Θ(n^2). Binary search, T(n) = T(n/2) + 1, is the balanced case with a = 1: Θ(log n). A traversal that visits both halves with constant extra work, 2T(n/2) + 1, is Θ(n).

Merge sort and counting. During a merge, when an element is taken from the right half, every element still waiting in the left half is larger than it. So cross pairs that satisfy an order condition (inversions, smaller elements to the right) can be counted in bulk in the same linear pass, keeping O(n log n) overall. Track original indices when counts must be reported per element.

Quicksort and quickselect. Partitioning around a pivot puts smaller elements left and larger elements right, and the pivot lands in its final position. Quicksort recurses on both sides; quickselect recurses only into the side containing position k. With a uniformly random pivot, the expected size of the side kept shrinks by a constant factor, so the expected total work is a geometric series: O(n). The worst case is still O(n^2), for example a first-element pivot on sorted input. Median of medians guarantees O(n) worst case with larger constants. Random pivots do not rescue a two-way partition that sends all keys equal to the pivot to one side: an array of identical keys stays quadratic, so use three-way partitioning.

Exponentiation by squaring. x^n = (x^(n/2))^2, times x when n is odd: T(n) = T(n/2) + O(1), so O(log n) multiplications. Handle n < 0 by inverting x, and remember that negating the most negative 32-bit integer overflows in fixed-width languages.

Divide and conquer versus DP. If the same subproblem recurs across branches, as in naive Fibonacci, plain recursion repeats work exponentially; caching results turns it into dynamic programming. Divide and conquer fits when subproblems are disjoint.

Common misconceptions

• "Quickselect is O(n)." It is expected O(n) with random pivots and O(n^2) in the worst case; say both, and mention median of medians for a worst-case guarantee.
• "Any recursion that halves the input is O(log n)." Halving with linear combine work is O(n log n), and recursing into both halves with constant work is O(n). Write the recurrence.
• "The master theorem solves every recurrence." It needs equal-sized subproblems shrinking by a constant factor; uneven splits and subtractive recurrences need recursion trees or substitution.
• "Merge sort needs O(n log n) extra memory." One auxiliary buffer of size n suffices, plus O(log n) stack for arrays.
• "Random pivots make quicksort immune to bad inputs." They make unlucky splits improbable for any input order, but many equal keys still need three-way partitioning.

How to approach it

Before coding, state the split, the recursive calls and the combine step, and write T(n). When asked for the k-th largest element, offer a size-k heap (O(n log k)) and quickselect (expected O(n)), then say which you will implement and why. For counting problems over pairs, ask whether a merge pass can count the cross pairs. Test recursive code on sizes 0, 1 and 2 and on duplicates. Mid and senior interviewers may ask how to make the worst case robust or how the approach parallelizes; independence of subproblems is the reason it does.