Intuition The one core ideaA big problem of size n smaller copies of the same problem , solving those, and cheaply gluing the answers back together. Divide and conquer is nothing more than this bet — split + glue is cheaper than brute force — plus the bookkeeping (a recurrence) that tells us exactly how fast the bet pays off.
Before you can read a single line of the parent note , you need to own every symbol it throws at you. This page builds each one from the ground up: plain words → a picture → why the topic even needs it. Nothing is assumed.
n n how big the thing you must process is . For a list to sort, n n
The picture: imagine a row of boxes. Count them. That count is n
Intuition Why we need a "size"Every claim about speed — "this is fast", "this is slow" — is meaningless unless we say fast for what size? Sorting 3 items is trivial; sorting 3 billion is not. The whole subject is about how the effort grows as n , so n
When we divide, two separate numbers describe the split. Do not confuse them.
a a a = 2 a = 3
b smaller each piece is)
Each subproblem has size about n / b n /2 b = 2 b divide the size by — it is about size , not count.
Common mistake Steel-man: "a b Why it feels right: in mergesort you cut into 2 halves and recurse on both, so a = 2 b = 2 happen to match.
Why it's wrong: they measure different things. In Karatsuba you cut each number into 2 halves (b = 2 a = 3 b = 2 a = 1 Fix: ask two separate questions — "how much smaller?" gives b "how many do I keep and solve?" gives a
Definition Recursion = a procedure that calls itselfA recursive procedure solves a problem by asking a smaller copy of itself to solve smaller pieces , then using those answers. The picture is a set of nested boxes: each box's job is to run smaller boxes and combine their outputs.
Definition Base case = the smallest problem, answered directlyThe base case is a size so small the answer needs no recursion — a list of length 1 floor that stops the nesting.
Intuition Why the base case is not optionalWithout a floor, the boxes nest forever — the program either runs endlessly or crashes (a stack overflow , when the pile of paused calls grows past memory). The base case is the only thing that guarantees the recursion ever stops . The parent note's first "steel-man" is entirely about this trap.
You will meet full recursion machinery again in Mathematical Induction and see it powering Mergesort , Quicksort , and Binary Search .
Definition Combine = gluing sub-answers into the whole answerOnce the a merge : walking two sorted halves and interleaving them into one sorted list.
f ( n ) f ( n ) not a recursive call: the work to split (divide) plus the work to glue (combine), for a problem of size n
Intuition Why bundle divide and combine together?When we later add up the cost, only two kinds of work exist: work done inside recursive calls , and work done here, now, at this level . Calling the second kind f ( n ) "my time = my subcalls' time + my own local work."
T ( n ) n T n guarantee , never an underestimate.
You will learn to actually solve such equations in Recurrence Relations .
log b n n b 1 n b b 1 number of divisions is log b n b n
Concrete: with b = 2 n = 8 8 → 4 → 2 → 1 3 steps, so log 2 8 = 3
Intuition Why logs appear everywhere hereSplitting repeatedly by b tree of levels . The height of that tree — how deep the nesting goes before hitting the base case — is exactly the number of halvings, log b n "how tall is the recursion?" That is the tool we need, and no simpler tool answers "how many times can I halve?"
a i a i i a a 0 1 1 a i a i
Intuition The watershed in one sentenceEvery recurrence is a tug-of-war between the leaves (many tiny problems, cost n l o g b a the local work f ( n ) . Whichever grows faster with n T ( n )
Definition The three growth symbolsThese describe how a cost grows with n , ignoring constant factors and small terms.
O ( g ) no faster than g Ω ( g ) no slower than g Θ ( g ) exactly like g
Intuition Why ignore constants?A step taking 3 n 10 n straight line in n shape — the thing that decides who wins as n → ∞ shapes , which is what scaling is about. Full details live in Big-O Notation .
log base b of n = tree height
watershed exponent log base b of a
Divide and Conquer analysis
Everything upstream feeds the two things the parent note actually does : prove correctness (via recursion = Mathematical Induction ) and find speed (via the recurrence + Master Theorem , applied to Mergesort , Binary Search , Karatsuba , Strassen Matrix Multiplication , and contrasted with Dynamic Programming ).
Test yourself — cover the right side and answer out loud.
What does n The size of the input (e.g. number of items in the list).
What is a The number of subproblems you actually solve after splitting.
What is b The factor the input size shrinks by; each subproblem has size n / b
Why can a = b They count different things — b a b = 2 a = 1
What is a base case and why is it required? The smallest input, answered without recursion; it is the floor that stops the nesting so the program terminates.
What is f ( n ) The non-recursive local work at one level: divide cost plus combine cost.
Read the recurrence T ( n ) = a T ( n / b ) + f ( n ) The time for size n a n / b
What does log b n The number of times you divide n b 1
What is c crit = log b a The watershed exponent; n l o g b a f ( n )
What do O Ω Θ Grows no faster than (ceiling), no slower than (floor), and exactly like (tight) the given function.
Recall Quick self-quizIf n = 16 b = 2 log 2 16 = 4 a = 3 log 2 n 3 l o g 2 n = n l o g 2 3 ≈ n 1.585
