Intuition The ONE core ideaA recursive algorithm does its total work by spawning smaller copies of itself, and the whole runtime is just the sum of the tiny bits of work done at every single call . The recursion tree draws all those calls as a family tree of jobs so you can see and add up the work — row by row — instead of guessing.
Before you can read the parent note , you need to own every letter it throws at you. This page builds each one from nothing: plain words → a picture → why the topic can't live without it . Read top to bottom; each item leans on the one above.
n n count of how many things your algorithm must handle. Sorting n n
Think of n length of a row of boxes you must process. When we say "cost n n
Why the topic needs it: every recursion tree question is "how does the work scale as n → ∞
f ( n ) f rule that takes a size and returns a cost . Feed it a problem of size m f ( m ) non-recursive work that one call does — the work it does itself , ignoring the work it hands to smaller calls.
f meter you clip onto one call . It reads only the effort spent inside that call — the splitting and combining — not the effort of its children.
Common meters you'll meet:
f ( n ) = n f ( n ) = n 2 n × n f ( n ) = 1
Why the topic needs it: the value written inside every tree node is f ( size of that node ) f
T ( n ) n T ( n ) grand total of all work an algorithm does on an input of size n
T f f ( n ) one call by itself . T ( n ) that call plus everyone it triggers . f T
Why the topic needs it: the entire method exists to compute T ( n )
Definition Recurrence relationA recurrence is an equation where T both sides , describing T ( n ) T smaller inputs. The star example:
T ( n ) = a T ( n / b ) + f ( n ) .
Read it in plain English: "The work on size n a n / b f ( n )
Intuition Why "self-referential" is the whole problemYou cannot just read off T ( n ) T unfold the equation: replace each T ( n / b ) is that unfolding drawn out. See Substitution Method for the algebra version of the same unfolding.
Why the topic needs it: a recursion tree is literally the picture of one recurrence being unrolled.
a a how many smaller subproblems each call creates. In T ( n ) = a T ( n / b ) + f ( n ) a T a ≥ 1
a fan-out of the family tree: one parent, a a = 2
Why the topic needs it: a width — how many nodes sit at each depth, hence how many meters you sum per row.
b n / b b factor the size divides by on the way down. It satisfies b > 1
b step size going down . With b = 2 n → n /2 → n /4 → … b = 4 n → n /4 → n /16
Why the topic needs it: b depth — how fast the size falls to 1
x i x i a i i times a ⋅ a ⋯ a a 0 = 1
Two powers do all the heavy lifting:
a i i a i − 1 a b i i i n / b i
Powers show up because the tree does the same multiplication at every level : × a ÷ b i is raising to the i
We also write f ( n ) = n d d = 1 n d = 2 n 2 d
Why the topic needs it: the whole verdict hinges on comparing the growth a i b d i
log b n n b 1 b log b n = i b i = n undoes the power: logs and exponents are opposite operations.
Intuition Why THIS tool and not anotherWe need the depth i n / b i 1 n / b i = 1 b i = n i = log b n forced , not chosen.
log b n number of steps down the shrinking staircase until each box is a single box. Steeper staircase (bigger b
Two facts you'll reuse:
log b n very slowly — doubling n All bases differ by a constant: log 3 n log 3/2 n Θ ( n log n )
Why the topic needs it: depth = log b n Binary Search for the simplest place a log
Definition Number of leavesThe bottom row has a depth = a l o g b n n l o g b a count of leaves , each doing Θ ( 1 )
The leaves are the tiniest jobs at the very bottom . There are usually a huge number of them. When they outnumber everything, their combined Θ ( 1 )
Why the topic needs it: one of the three outcomes is "leaves win", and its size is exactly n l o g b a
Definition Geometric seriesA geometric series adds terms where each is a fixed ratio r c ( 1 + r + r 2 + ⋯ ) r = a / b d
Intuition Why this decides the answerPer-level work = n d ( a / b d ) i r = a / b d
r < 1 shrink downward → root wins → Θ ( f ( n )) r = 1 equal → multiply by log b n log r > 1 grow downward → leaves win → Θ ( n l o g b a )
This is the Master-Theorem verdict, derived from one series. See Geometric Series and Master Theorem .
Why the topic needs it: deciding "who dominates" is asking which way the geometric series tips.
Definition Asymptotic notationThese describe growth as n → ∞
O ( g ) at most like g Ω ( g ) at least like g Θ ( g ) exactly like g
Imagine two curves. O g Θ g Θ true growth rate.
Why the topic needs it: the recursion tree's output is always stated as Θ ( … ) Big-O Notation .
level work a to i times f
geometric series ratio a over b to d
Read it as: the four ingredients (n , f , a , b a b
Self-test: can you answer each without peeking?
What does n Input size — a row of n
What is the difference between f ( n ) T ( n ) f ( n ) T ( n )
In T ( n ) = a T ( n / b ) + f ( n ) a b a b
Why is the tree depth log b n Because size at level i n / b i 1 b i = n i
How many nodes and how many leaves does the tree have at depth i a i i a l o g b n = n l o g b a
What is the ratio of a recursion tree's geometric series, and what do r < 1 , r = 1 , r > 1 r = a / b d r < 1 r = 1 log r > 1
Why do we state the final answer with Θ The tree reveals growth shape, not exact constants, so Θ