Lesson 165
Divide and Conquer
Divide · Conquer · Combine
1:00How to design fast algorithms by breaking a problem into smaller copies of itself, solving them recursively, and combining the results — illustrated through merge sort, quick sort, Karatsuba multiplication, and the Master Theorem.
By the end, you can
- Identify and label the divide, conquer, and combine steps in any divide-and-conquer algorithm.
- Explain why a missing base case causes infinite recursion and a stack overflow.
- Trace the recursion tree for merge sort and determine its depth for a given n.
- Describe how merge sort's linear merge step combines with log n levels to give O(n log n).
- Explain why quick sort degrades to O(n²) when the pivot is always the min or max element.
- Distinguish divide and conquer (two or more sub-problems, combine) from decrease and conquer (one sub-problem, no combine), using binary search as the canonical example.
- Apply the Master Theorem to solve T(n) = a·T(n/b) + f(n) for binary search, merge sort, Karatsuba, and naive matrix multiply.
- Explain how Karatsuba saves one multiplication per level and why that changes the overall exponent.
- Name two major algorithms beyond sorting (FFT, Strassen) that use the divide-and-conquer paradigm.
- List the four signals that suggest divide and conquer is the right approach, and the four main trade-offs.
Up next in Algorithms & Graph Algorithms
