The Master Theorem provides the asymptotic complexity for recurrences of the form T(n) = aT(n/b) + f(n), where a ≥ 1 and b > 1. It compares the work done dividing and combining (f(n)) against the work saved by recursion (n^(log_b(a))). The three cases capture whether the recursion depth dominates, they're balanced, or the combining cost dominates. Merge sort: a=2, b=2, so n^(log₂(2)) = n, giving T(n) = Θ(n log n).

Quicksort is usually preferred because it has smaller constant factors and is cache-friendly due to in-place partitioning. Mergesort requires allocating O(n) extra space for merging. However, quicksort's worst case is O(n²) (bad pivots), while mergesort guarantees O(n log n). For applications requiring guaranteed performance, mergesort's predictability wins. Many standard library sorts (like Python's Timsort) are hybrid approaches.

Use divide and conquer: If medians are equal, that's the combined median. If median1 > median2, the median must be in the left half of array1 and right half of array2 (and vice versa). Recursively eliminate halves until you've narrowed down to O(1) elements. Complexity is O(log n)—much better than merging (O(n)) then finding median. The key insight is that we're partitioning, not merging.

Strassen's algorithm multiplies two n×n matrices in O(n^(2.81)) instead of the naive O(n³). It reduces the number of recursive matrix multiplications from 8 to 7 by computing intermediate matrices. While theoretically significant (first improvement over naive multiplication), the constants make it slower than optimized naive for practical sizes. It exemplifies how asymptotic improvements don't always translate to practical speedups.

Although both use recursion to break problems into subproblems, the key difference is subproblem independence. Divide and conquer splits into independent subproblems with no overlap — merge sort's left and right halves are sorted independently. Dynamic programming solves overlapping subproblems, where the same subproblem appears multiple times (e.g., Fibonacci numbers). DP uses memoization or tabulation to avoid redundant work; divide and conquer doesn't need it. DP typically solves optimization problems (shortest path, knapsack), while divide and conquer solves computational problems (sorting, searching, FFT).

The algorithm works in five steps: (1) Sort all points by x-coordinate. (2) Divide the set into two halves by a vertical line through the median x. (3) Recursively find the minimum distance d in the left and right halves. (4) Let d = min(d_left, d_right). (5) Check points within a vertical strip of width 2d around the dividing line — these are the only candidates for a closer pair that crosses the divide. Within the strip, sort points by y-coordinate and compare each point with at most 6 following points. Total complexity is O(n log n). The key insight is that only a constant number of comparisons are needed in the strip check, keeping the combine step O(n).

Karatsuba multiplication multiplies two n-digit integers in O(n^(log₂3)) ≈ O(n^(1.585)), which is asymptotically faster than the O(n²) grade-school method. The trick: to multiply two n-digit numbers, split each into high and low halves: x = a·B + b, y = c·B + d. Instead of computing ac, ad, bc, bd (four multiplications), Karatsuba computes three multiplications: ac, bd, and (a+b)(c+d). The middle term ad+bc = (a+b)(c+d) - ac - bd, saving one multiply. For large integers (thousands of bits), this asymptotic improvement matters. It was the first multiplication algorithm faster than O(n²) and kicked off the "multiplication algorithm race" leading to FFT-based methods.

The Cooley-Tukey FFT algorithm applies divide and conquer to compute the Discrete Fourier Transform (DFT) in O(n log n) instead of O(n²). It splits the input sequence into even-indexed and odd-indexed terms, recursively computes the DFT of each half, and combines them using the periodicity and symmetry properties of the complex roots of unity (the "twiddle factors"). The combine step is O(n) because each frequency component combines one even and one odd term multiplied by a complex exponential. FFT is used in JPEG compression, MP3 encoding, large-integer multiplication, and solving partial differential equations.

Beyond sorting and searching, divide and conquer powers: (1) Fast Fourier Transform — the foundation of JPEG, MP3, Wi-Fi (OFDM), and MRI image reconstruction. (2) Strassen's matrix multiplication — used in scientific computing and machine learning for large matrix operations. (3) Closest pair of points — used in GIS systems, collision detection, and astronomy. (4) Karatsuba multiplication — used in cryptographic libraries (RSA, Diffie-Hellman) for large-integer arithmetic. (5) FFT-based polynomial multiplication — used in barcode scanners and error-correcting codes. (6) Parallel computing frameworks (MapReduce, Apache Spark) use divide and conquer at the architectural level — split data, process in parallel, merge results.

The maximum subarray problem finds the contiguous subarray with the largest sum. The divide and conquer solution splits the array at the midpoint and considers three cases: (1) maximum subarray entirely in the left half, (2) entirely in the right half, (3) crossing the midpoint. Cases 1 and 2 are recursive calls. Case 3 computes the maximum suffix sum in the left half and the maximum prefix sum in the right half, then adds them. The result is the maximum of the three cases. Complexity is O(n log n) — though Kadane's O(n) algorithm is better in practice, the divide and conquer approach demonstrates the "combine" step well and is useful for teaching.

To convert a recursive divide and conquer algorithm to iterative: (1) Use an explicit stack (or queue) that stores subproblem state instead of relying on the call stack. For merge sort, this means pushing array segments to process. (2) For divide-then-combine patterns, use a post-order traversal approach — push all subproblems first, then pop and combine results. (3) For algorithms like binary search, the iterative version is straightforward (while loop with low/high pointers). (4) For algorithms like merge sort, use bottom-up iteration: start with subarrays of size 1, iteratively merge pairs, doubling the size each step. The benefits are avoiding stack overflow, better performance (no function call overhead), and deterministic memory usage regardless of input structure.

The Master Theorem requires f(n) to be polynomially compared to n^(log_b(a)). Recurrences that don't fit include: (1) Non-polynomial f(n) like f(n) = n/log n — Akra-Bazzi theorem handles this. (2) Different subproblem sizes where subproblems aren't equal (T(n) = T(n/2) + T(n/4) + n) — requires iteration or Akra-Bazzi. (3) Fractional subproblem counts — Akra-Bazzi: T(x) = sum(a_i T(b_i x)) + f(x). (4) Subtract-and-conquer where recurrence is T(n) = aT(n - b) + f(n) — use iteration method or change of variables. For recurrences outside Master Theorem's domain, drawing a recurrence tree or using iteration is often the most practical approach.

The Akra-Bazzi theorem solves T(x) = sum(a_i T(b_i x)) + f(x) where 0 < b_i < 1. It finds p such that sum(a_i * b_i^p) = 1, then gives T(x) = Theta(x^p + x^p integral(f(x)/x^(p+1)) dx). You need it when: (1) Subproblems have different sizes (T(n) = T(n/3) + T(n/2) + O(1)). (2) More than two subproblems exist with unequal splits. (3) f(n) isn't polynomial. For balanced equal-split recurrences (like merge sort or binary search), Master Theorem is simpler and gives the same answer. Example: T(n) = T(n/2) + T(n/4) + n — Akra-Bazzi gives T(n) = Theta(n) because p=0 and the integral yields n.

Cache-oblivious algorithms use divide and conquer to achieve optimal cache performance without knowing the cache size M. The key insight: recursively dividing the problem means data access patterns naturally exhibit locality at all cache levels simultaneously. For example, matrix transpose using recursive subdivision — the same algorithm is optimal for L1, L2, and RAM because the recursion naturally aligns working sets to each cache level. Cache-aware approaches (like blocking for BLAS operations) explicitly tune to M and B, achieving lower constants but requiring tuning. Cache-oblivious is simpler, portable, and asymptotically optimal — but cache-aware can win in practice when cache parameters are known and stable. The Funnel Sort algorithm achieves O((n/B) log_(M/B)(n)) I/Os — optimal for comparison sorting.

Divide and conquer parallelizes naturally when subproblems are independent. For merge sort: split array, sort halves in parallel (ForkJoinPool or thread pool), merge results. Expected speedup: with p processors, T_p = T(n/p) + O(n) for merging, giving O(n log n/p + n) — near-linear speedup for large n, but merging becomes the bottleneck at high parallelism. Key considerations: (1) Work stealing — assign subproblems to idle threads dynamically. (2) Grain size — stop parallelizing below a threshold (typically 1000-5000 elements) where overhead exceeds benefit. (3) Merge bottleneck — with many threads, merge O(n) becomes limiting; use parallel merging (split merge into chunks, merge in parallel). (4) Amdahl's law — the sequential merge step limits maximum speedup to roughly 1/(1 - s) where s is the fraction that's sequential.

Top-down recursively decomposes the problem (merge sort: split until single elements, then combine). Bottom-up starts from base cases and builds upward (merge sort: start with pairs, merge to quadruples, doubling each step). Top-down wins when: (1) Subproblem decomposition is complex or data-driven. (2) You need early termination (pruning). (3) Problem structure isn't known until runtime. Bottom-up wins when: (1) Recursion overhead matters (small constant factors). (2) Cache locality is critical — bottom-up's sequential passes through data are very cache-friendly. (3) Recursion depth could cause stack overflow. Timsort (Python, Java) is a hybrid: bottom-up runs insertion sort on small chunks, then top-down merges the sorted runs — combining bottom-up's locality with top-down's structural clarity.

Quickselect uses divide and conquer to find the kth smallest element in expected O(n) time — same partitioning as quicksort. Choose a pivot, partition the array (like quicksort), then recursively search only the partition that contains the kth element. If the pivot lands exactly at position k-1, you're done. The expected recurrence is T(n) = T(n/2) + O(n), solving to O(n). Worst case is O(n²) when the pivot is always the smallest or largest element. Mitigations: (1) Median of medians — pick pivot as the median of groups of 5, guaranteeing O(n) worst case but higher constant factors. (2) Randomized pivot — expected O(n), practical constant better than median of medians. Use when: you need order statistics and can't afford full sort (O(n log n)), and worst-case O(n²) is unacceptable but average-case O(n) is acceptable.

Tournament elimination finds both min and max in at most ceil(3n/2) - 2 comparisons — better than the naive 2(n-1). Divide and conquer approach: pair up elements, compare each pair, record winner and loser. The winners form a smaller set (n/2 elements) where the minimum must be. Recurse to find the global minimum. Then find the global maximum by following the path from the minimum element up through the tournament tree — the maximum must be among elements that lost to smaller elements. This divide-and-conquer tournament structure achieves the information-theoretic lower bound for this problem. It's optimal: you can't determine both min and max in fewer comparisons because you need enough comparisons to distinguish the unique smallest and unique largest from n candidates.

Case 3 of the Master Theorem requires two conditions: (1) f(n) = Omega(n^(log_b(a) + epsilon)) for some epsilon > 0 (polynomially larger), and (2) a*f(n/b) <= c*f(n) for some c < 1 (regularity condition). The regularity condition ensures the combining work doesn't grow faster than the subproblem reduction. When violated — for example, if f(n) = n * 2^n and a=2, b=2, then a*f(n/b) = 2*(n*2^(n/2)) which is NOT O(f(n)) — the Master Theorem case 3 doesn't apply. The recurrence T(n) = 2T(n/2) + n*2^n blows up superpolynomially because each level adds exponentially more work than the previous one. Practical approach: use iteration to analyze such recurrences — draw the recurrence tree to see how costs compound at each level.

Standard Lomuto partition with a single pivot creates O(n) equal elements that all go to one side, causing O(n²) behavior on inputs with many duplicates. Dutch National Flag (three-way) partitioning splits into < pivot, == pivot, and > pivot. This groups equal elements in their final position immediately, so they never participate in further recursive calls. Time complexity becomes O(n log n) for inputs with n distinct values, O(n) for inputs where all values are equal — better than standard quicksort's O(n log n) average but pathological O(n²) worst case. This is exactly how Java's Dual-Pivot Quicksort (since Java 7) works, and it's why many modern sorting libraries use three-way partitioning as the default. The combine step is trivial since equal elements are already placed — no merging needed.