Basic D&C Questions

Six warm-ups to lock the split/conquer/combine pattern into muscle memory. Each one is a direct application of one of the four canonical recurrence shapes — by the end you should be able to write the recurrence for a new problem before you write any code.

1. Power function `pow(x, n)`

Compute x^n for integer n.

Shape: T(n) = T(n/2) + O(1) → O(log n). One recursive call (half the exponent), constant combine.

Time: O(log n). Space: O(log n) recursion stack.

2. Find the maximum in an array (recursively)

Shape: T(n) = 2 T(n/2) + O(1) → O(n). Two recursive calls, constant combine.

Time: O(n). Space: O(log n) recursion.

The iterative for x in arr: best = max(best, x) is just as good (and uses O(1) space). The D&C version is useful when the combine step is non-trivial (e.g., “max plus the index of the max”) or when parallelism matters.

3. Recursive sum

Compute the sum of an array.

Same T(n) = 2 T(n/2) + O(1) → O(n). The recursive version is interesting for the same reason as find-max — it’s the building block for parallel sum reductions on GPUs and distributed systems.

4. Binary Search (recursive)

Find a target in a sorted array.

Shape: T(n) = T(n/2) + O(1) → O(log n).

Time: O(log n). Space: O(log n).

For production code, prefer the iterative version (see Day 13).

5. Count nodes in a binary tree

Shape: T(n) = 2 T(n/2) + O(1) (assuming balanced) or T(n) = T(left) + T(right) + O(1) (general) → O(n).

Time: O(n). Space: O(h) recursion stack (tree height).

This is the cleanest D&C example in the chapter — three lines, base case + two recursive calls + one-line combine.

6. Merge two sorted arrays

Given two sorted arrays, return the merged sorted result.

Not strictly recursive D&C, but it’s the combine step of merge sort and the foundation for every “two-pointer on two arrays” problem.

Time: O(n + m). Space: O(n + m) for the output.

Reuse this everywhere — sorting, merge-based inversion counting, k-way merges (with a heap), polynomial addition, set union on sorted lists.

Mini-quiz

For the recursive find-max algorithm, the recurrence is T(n) = 2 T(n/2) + O(1). Why isn't this O(log n) like binary search?

In fast exponentiation pow(x, n), what's the harm in using `pow(x, n-1) * x` instead of `pow(x, n/2)`?

For count_nodes in a tree, the recurrence is T(n) = T(left_size) + T(right_size) + O(1). Why does this give O(n) regardless of tree shape?

Next: the ten practice problems — every D&C shape represented, with the recurrence written out for each.

Advanced Patterns Overview