DSA & Algorithms
Part 9 of 16 · DSA Advanced & Company FavoritesRecursion & Divide-and-Conquer - Master theorem intuition, merge patterns
Divide-and-conquer templates, merge patterns, Master theorem intuition for interview analysis.
- 1Gist
- 2Maps
- 3Q&A
- 4Sandbox
Voice readout needs Web Speech Synthesis in this browser.
The same problem on a smaller size combines
Prefer
Split, recurse, combine
Write the recurrence, then the combine cost.
- Merge sort combine is linear.
- Pow squares the exponent.
- Master theorem names the case after you have a and b.
Alternative
One loop over the whole input
Some of these problems are iterative, and the prompt still wants the split.
- You recurse without a smaller size.
- You combine in quadratic time and still quote n log n.
- You skip the base case.
Write the recurrence first
Then the code matches a, b, and f(n).
- 1
Split into a parts
Each part has size n/b. - 2
Solve the parts
Base case when the size is constant. - 3
Combine
This cost is f(n). It decides the case.
Overview
Divide-and-conquer templates, merge patterns, Master theorem intuition for interview analysis.
When companies ask this
Recognition cues: merge sort style count inversions; majority vote variants; pow; different ways to add parentheses; sort list.
Mental model
Flow
- 1
1. Size n
- next2. Split into a parts of n/b
- 2
2. Split into a parts of n/b
- next3. Solve each part
- 3
3. Solve each part
- next4. Combine, cost f of n
- 4
4. Combine, cost f of n
Lesson map
Recursion & Divide-and-Conquer - Master theorem intuition, merge patterns
Divide-and-conquer templates, merge patterns, Master theorem intuition for interview analysis.
Architecture. 1. Size n Ready. 2. Split into a parts of n/b Ready. 3. Solve each part Ready. 4. Combine, cost f of n Ready
Select a node to see why it exists, or an edge to see the protocol, direction, effect, and consequence.
Mermaid export
flowchart TB Problem["1. Size n Ready"] Split["2. Split into a parts of n/b Ready"] Conquer["3. Solve each part Ready"] Combine["4. Combine, cost f of n Ready"] Problem -->|continues| Split Split -->|continues| Conquer Conquer -->|continues| Combine
Master theorem intuition: T(n)=a T(n/b)+f(n). Compare f with n^(log_b a): poly smaller -> n^(log_b a); same -> n^(log_b a) log n; larger (regularity) -> Theta(f).
Core template (Python)
Press Run. Snippets must be self-contained — no network, files, or native modules.
Core template (TypeScript)
Press Run. Snippets must be self-contained — no network, files, or native modules.
Complexity + pitfalls
- Merge sort O(n log n); pow O(log n).
- Pitfalls: stack overflow on deep recursion; off-by-one mid; expensive combine ignored in analysis.
Interviewer traps
LeetCode drill (real problems)
- Sort an Array
- Sort List
- Pow(x, n)
- Majority Element
- Different Ways to Add Parentheses
- Beautiful Array
- Burst Balloons
- Count of Smaller Numbers After Self
- Convert Sorted Array to Binary Search Tree
YouTube
Interview Q&A
Master theorem use?
Answer
Quick asymptotics for aT(n/b)+f(n).
Merge sort recurrence?
Answer
T(n)=2T(n/2)+O(n) -> O(n log n).
Inversions?
Answer
During merge, when right[j] < left[i], add len(left) - i (every remaining left value is larger).
vs DP?
Answer
D&C independent subproblems; DP overlapping.
Tail recursion?
Answer
Language may not optimize; prefer iterative pow.
Related wave-1?
Answer
binary-search, trees-dfs, sorting.
Quickselect?
Answer
Expected O(n) with a random pivot, worst case O(n^2); median-of-medians guarantees O(n).
Interval DP link?
Answer
Burst balloons is DP but D&C-shaped recurrence.