Algorithms
Divide and Conquer (Intro)
Difficulty: Intermediate
Merge sort and quick sort both run in O(n log n), and once you write down their recurrences (T(n) = 2T(n/2) + O(n) and its expected-case sibling) the same n log n falls out of both. That is not a coincidence: divide and conquer is a...
Divide and Conquer (Intro)
Merge sort and quick sort both run in O(n log n), and once you write down their recurrences (T(n) = 2T(n/2) + O(n) and its expected-case sibling) the same n log n falls out of both. That is not a coincidence: divide and conquer is a paradigm with a precise mathematical signature, and the Master Theorem reads it directly off the recurrence.
Divide and Conquer (Intro) introduces the three-step pattern (divide, conquer, combine) and the recurrence-relation toolkit that comes with it. You will analyze merge sort and quick sort as canonical D&C algorithms, look at binary search through the same lens, walk through the divide-and-conquer maximum subarray algorithm, and meet the closest-pair-of-points problem in 1D. Along the way the lesson formalizes the Master Theorem template T(n) = aT(n/b) + f(n) and shows you how to read time complexity off it without solving the recurrence by hand. It also draws the line between D&C (independent subproblems) and DP (overlapping subproblems) so you can spot which paradigm fits.
In Recursion Fundamentals, you saw recursion as one frame calling another. D&C is the case where a frame makes multiple recursive calls and combines their results.
Next, Matrix Algorithms turns to two-dimensional arrays.
Prerequisites:
Recursion FundamentalsTopics:
What You'll Learn
By the end of this lesson, you will be able to:
Describe the three steps of divide and conquer: divide, conquer, and combine.
Analyse merge sort and quick sort as divide-and-conquer algorithms and write their recurrence relations.
Implement the maximum subarray sum problem using a divide-and-conquer approach.
Apply the Master Theorem to determine the time complexity of D&C recurrences.
Explain why binary search is a special case of divide and conquer.
Distinguish divide and conquer from dynamic programming based on subproblem independence.
Why This Matters
01
Merge sort and quick sort — two of the most important sorting algorithms — are both divide-and-conquer algorithms, and understanding D&C explains why they achieve O(n log n).
02
Binary search is D&C in disguise: divide the search space in half, conquer the relevant half, combine is trivial.
03
The Master Theorem lets you instantly determine the time complexity of any D&C recurrence of the form T(n) = aT(n/b) + O(n^d).
04
Distinguishing D&C (independent subproblems) from DP (overlapping subproblems) helps you choose the right paradigm quickly in interviews.
Key Terms
6 terms you'll encounter in this lesson
Divide
The first step of D&C: split the problem into smaller subproblems of the same type, typically by halving the input.
Conquer
The second step of D&C: solve each subproblem recursively. Base cases are solved directly.
Combine
The third step of D&C: merge subproblem solutions into a solution for the original problem. This is often where the main work happens.
Recurrence relation
A mathematical equation that expresses the running time of a recursive algorithm in terms of smaller inputs, e.g. T(n) = 2T(n/2) + O(n) for merge sort.
Master Theorem
A formula for solving recurrences of the form T(n) = aT(n/b) + O(n^d). Compares log_b(a) with d to determine if the answer is O(n^d log n), O(n^(log_b a)), or O(n^d).
Cross-boundary subarray
In the maximum-subarray D&C approach, the subarray that spans both the left and right halves. Finding its sum requires a linear scan from the midpoint outward in both directions.
Heads Up
Common misconceptions to watch out for
"Divide and conquer is just recursion"
All D&C uses recursion, but not all recursion is D&C. D&C specifically requires three steps: divide into independent subproblems, conquer recursively, and combine. Simple recursion like factorial does not divide the problem into multiple independent parts.
"D&C always gives O(n log n) time"
The time depends on the recurrence. Merge sort is O(n log n) because T(n) = 2T(n/2) + O(n). But binary search is O(log n) because T(n) = T(n/2) + O(1) — only one subproblem. Quick sort worst case is O(n^2) with bad pivots.
"D&C and DP are interchangeable"
D&C works when subproblems are independent (no overlap). DP is needed when subproblems overlap and the same subproblem is solved multiple times. Using D&C on overlapping problems leads to exponential time (like naive Fibonacci). Using DP on independent problems wastes memory on a cache that never gets a hit.