Unit 2: Divide and Conquer

General recurrence: T(n) = a·T(n/b) + D(n) + C(n), where D and C are the divide and combine costs.

• Binary search compares the key with the middle element and recurses on one half: T(n) = T(n/2) + 1 = O(log n).
• Max-min (divide and conquer): split the array into halves, find the max and min of each, then compare the two results. It needs 3n/2 − 2 comparisons, fewer than the 2n − 2 of the straightforward method.

Divide the array into two halves, sort each recursively, then merge the two sorted halves.

• T(n) = 2T(n/2) + n = Θ(n log n) in all cases.
• Stable, but needs O(n) extra space for merging.

Choose a pivot, partition the array so smaller elements are on its left and larger on its right, then recursively sort both parts.

Quick sort sorts in place and is usually faster in practice than merge sort; randomised or median-of-three pivots avoid the worst case.

Ordinary divide and conquer multiplies n × n matrices with 8 multiplications of n/2 × n/2 blocks: T(n) = 8T(n/2) + n² = O(n³). Strassen's method uses only 7 multiplications (with extra additions): T(n) = 7T(n/2) + n² = O(n^2.81). Lower bound for comparison sorting: any comparison-based sort can be modelled as a decision tree with at least n! leaves; its height is at least log₂(n!) = Ω(n log n). So no comparison sort can beat n log n in the worst case — merge sort and heap sort are optimal.