CS21203: Algorithm 1
Topic: The Recursion Tree Method
CSE Department, IIT Kharagpur
Teacher: Sudeshna Sarkar
Date: 21 July 2026
CSE, IIT Kharagpur CS21203 Lecture 2: Recurrence & Substitution Method 1/19
Today’s Roadmap
1. Why substitution alone isn’t enough
2. Building a recursion tree
3. Balanced trees: geometric sums
4. Unbalanced trees
5. Pitfalls
Goal for this lecture
Stop guessing bounds out of thin air. The recursion tree generates a guess – verifying it
rigorously (if needed) is still Lecture 2’s substitution method.
CSE, IIT Kharagpur CS21203 Lecture 2: Recurrence & Substitution Method 2/19
Recap: Where Substitution Left Us
Last lecture, the substitution method gave us a rigorous way to verify a guessed bound.
The gap we ended on
Substitution never tells you what to guess. For T (n) = 2T (n/2) + n, most of you produced the
right intuition on the spot – a rough tree, log n levels, n work per level – but nobody turned
that sketch into a real proof unaided.
Today: formalize that sketch into a method (recursion tree) that reliably produces the guess.
(The theorem that skips the sketch entirely, for the common divide-and-conquer case, is next
lecture.)
Recursion trees don’t replace substitution – they feed it. Once you have a tree-generated guess,
substitution is still how you’d prove it airtight, if asked.
CSE, IIT Kharagpur CS21203 Lecture 2: Recurrence & Substitution Method 3/19
The Recursion Tree: Core Idea
Definition
A recursion tree is a diagram where each node represents the cost of one subproblem at the
moment it is divided excluding the cost of its children (which appear as separate nodes below
it).
• The root is the cost of dividing/combining at the original problem size n.
• Each level of the tree corresponds to one level of recursive calls.
• The recurrence T (n) = aT (n/b) + f (n) becomes: root cost f (n), with a children, each
solving a subproblem of size n/b.
• Total running time = sum of all node costs, over the entire tree.
Turning a recurrence into a tree converts an algebraic recurrence into a counting problem: how
many levels, how many nodes per level, what’s the cost per node.
CSE, IIT Kharagpur CS21203 Lecture 2: Recurrence & Substitution Method 4/19
Building a Recursion Tree: The Recipe
1. Draw the root: label it with f (n) : the non-recursive cost at the top level.
2. Give the root a children, each labeled with f (n/b) : the non-recursive cost of each
subproblem at the next level.
3. Recurse: each of those children gets a children of its own, at size n/b 2 , and so on.
4. Stop when the subproblem size hits the base case (constant size) – these are the leaves.
5. Sum every node in the tree, level by level, then sum over all levels.
The two numbers that matter most
• How many levels does the tree have?
• What is the total cost at each level, and how does it change level to level (growing,
shrinking, or constant)?
This pair determines everything else.
CSE, IIT Kharagpur CS21203 Lecture 2: Recurrence & Substitution Method 5/19
Worked Example 1: T (n) = 2T (n/2) + n — Building the
Tree
Reading the tree:
n • Root: cost n (one node, size n)
• Level 1: two nodes, each cost n/2
• Level 2: four nodes, each cost n/4
n/2 n/2
• Pattern: at level i, there are 2i nodes,
each of cost n/2i
n/4 n/4 n/4 n/4
Key observation: total cost at level i is
n
2i × i
= n.
|{z} 2
# nodes |{z}
cost/node
Every level costs exactly n – CSE,
this IIT
is the “balanced”
Kharagpur signature
CS21203 Lecture 2: to watch &
Recurrence for.
Substitution Method 6/19
Worked Example 1: How Many Levels?
Question: at what level does the recursion bottom out (subproblem size reaches 1)?
Subproblem size at level i is n/2i . Set this equal to the base case size:
n
=1 =⇒ 2i = n =⇒ i = log2 n.
2i
Tree depth
The tree has log2 n + 1 levels, indexed i = 0, 1, . . . , log2 n (root at i = 0, leaves at i = log2 n).
Leaves: at level log2 n, there are 2log2 n = n leaves, each representing a base case of cost Θ(1).
This depth computation – “set subproblem size to the base case and solve for i” – is the
standard move and will recur in every example today.
CSE, IIT Kharagpur CS21203 Lecture 2: Recurrence & Substitution Method 7/19
Worked Example 1: Summing the Tree
Total cost = sum of per-level costs, over all levels:
log2 n−1
X
T (n) = n + Θ(n)
| {z }
i=0 leaf level
| {z }
internal levels
The leaf level has n leaves, each Θ(1), contributing Θ(n) – matching the pattern (every level
costs Θ(n)).
Sum over levels: there are log2 n internal levels (level 0 through level log2 n − 1), each costing
exactly n:
T (n) = n · log2 n + Θ(n) = Θ(n log n).
This is a guess, not yet a proof
The recursion tree gives us strong evidence that T (n) = Θ(n log n) – but it involves informal
reasoning about “every level costs n” without induction. Lecture 2’s substitution method is how
you would make this airtight, as we already did for exactly this recurrence.
CSE, IIT Kharagpur CS21203 Lecture 2: Recurrence & Substitution Method 8/19
Closing the Loop with Lecture 2
Recursion tree guess: T (n) = Θ(n log n) Substitution
generates a guess verifies the guess
Recall from Lecture 2: we proved, by induction,
T (n) ≤ c n log n and T (n) ≥ c ′ n log n
for the same recurrence T (n) = 2T (n/2) + n – exactly the bound the tree just predicted.
The workflow, going forward
Recursion tree first (fast, informal, generates the guess) → substitution second (rigorous,
only if a formal proof is required). In practice, once you trust the tree method, you often skip
the second step – but you should always know you could do it.
CSE, IIT Kharagpur CS21203 Lecture 2: Recurrence & Substitution Method 9/19
Worked Example 2: T (n) = 3T (n/4) + n — Building the
Tree
Reading the tree:
n
• Root: cost n
• Level 1: 3 nodes, each cost n/4; level
total = 3 · n4 = 34 n
n/4 n/4 n/4 • Level 2: 9 nodes, each cost n/16;
2
n
level total = 9 · 16 = 34 n
n n n n
Unlike Example 1, level costs are
16 16 16 16
shrinking by a constant factor 34 each
level.
CSE, IIT Kharagpur CS21203 Lecture 2: Recurrence & Substitution Method 10/19
Worked Example 2: Depth and Per-Level Cost
General level-i cost: at level i there are 3i nodes, each of size n/4i , each costing Θ(n/4i ):
i
n 3
level-i cost = 3i · =n .
4i 4
Depth: subproblem size hits the base case when n/4i = 1, i.e. i = log4 n.
Series to sum
log4 n−1 i
X 3
+ Θ nlog4 3
T (n) = n
4
i=0
log4 n log4 3
The leaf count is 3 =n (each leaf Θ(1)), matching the last, smallest level.
CSE, IIT Kharagpur CS21203 Lecture 2: Recurrence & Substitution Method 11/19
Worked Example 2: Summing a Geometric Series
log4 n−1 i
X 3 3
The sum n is a geometric series with ratio r = 4
< 1.
i=0
4
Geometric series fact
k−1
X 1 − rk 1
ri = < (a constant, when r < 1, independent of k)
i=0
1−r 1−r
Applying this with r = 34 :
log4 n−1 i
X 3 1
T (n) = n + Θ(nlog4 3 ) < n · 3 + Θ(nlog4 3 ) = 4n + Θ(nlog4 3 ).
i=0
4 1− 4
Conclusion
Since log4 3 ≈ 0.79 < 1, the 4n term dominates: T (n) = Θ(n).
Pattern to notice: when level costs shrink geometrically, the root dominates the total – the sum is a
constant multiple of the root’s cost.
CSE, IIT Kharagpur CS21203 Lecture 2: Recurrence & Substitution Method 12/19
Worked Example 3: Unequal Subproblem Sizes
Recurrence: T (n) = T (n/3) + T (2n/3) + n (e.g., a poorly-pivoted divide step).
n/3 2n/3
Immediate complication: the two subtrees have different depths – the n/3 branch shrinks
to the base case faster than the 2n/3 branch.
This tree is unbalanced
Unlike Examples 1–2, there is no single, uniform “level i” cost – different root-to-leaf paths
have different lengths. We need a different strategy: bound the longest path, and bound the
cost per level (which is still easy here).
CSE, IIT Kharagpur CS21203 Lecture 2: Recurrence & Substitution Method 13/19
Worked Example 3: Bounding an Unbalanced Tree
Key fact that still holds: at every level, no matter how unbalanced, the subproblem sizes at
that level sum to at most n (since every node’s children sizes sum to the parent’s size, e.g.
n/3 + 2n/3 = n).
Consequence
Since the cost at each node is Θ(size), the total cost at any single level is at most cn for
some constant c – exactly like the balanced case, level cost = Θ(n)!
What differs from Example 1: the number of levels.
• Shortest root-to-leaf path: repeatedly take the n/3 branch ⇒ depth log3 n.
• Longest root-to-leaf path: repeatedly take the 2n/3 branch ⇒ depth log3/2 n.
The tree has between log3 n and log3/2 n levels – both are Θ(log n) (only the base of the log
differs, which is a constant factor).
CSE, IIT Kharagpur CS21203 Lecture 2: Recurrence & Substitution Method 14/19
Worked Example 3: Conclusion
Upper bound: every level costs O(n), and there are O(log n) levels (using the longest path,
log3/2 n):
T (n) = O(n log n).
Lower bound: every level costs Ω(n) (in fact, until the short branches start bottoming out,
every level costs exactly Θ(n)), and there are Ω(log n) levels (using the shortest path, log3 n):
T (n) = Ω(n log n).
Conclusion
T (n) = Θ(n log n) – the same answer as the perfectly balanced 2T (n/2) + n! The 1:2
split doesn’t change the asymptotic answer, only the constant inside the logarithm’s base
(which asymptotic notation absorbs).
Takeaway: for unbalanced trees, bound level-cost and shortest/longest path separately, then
sandwich.
CSE, IIT Kharagpur CS21203 Lecture 2: Recurrence & Substitution Method 15/19
Worked Example 4: A Linear (Chain) Recursion
Recurrence: T (n) = T (n − 1) + n (e.g. insertion sort’s worst case).
n−1
n−2
···
• Each node has exactly one child – this tree is a single chain, not a branching tree.
• There are n levels (one per unit decrease from n down to 1).
• Level i (counting from the root, i = 0, . . . , n − 1) has cost n − i.
n−1 n
X X n(n + 1)
Sum: T (n) = (n − i) = k= = Θ(n2 ).
i=0
2
k=1 CSE, IIT Kharagpur CS21203 Lecture 2: Recurrence & Substitution Method 16/19
Matches Lecture 2’s substitution result for this exact recurrence.
The Recursion Tree Method: General Recipe
1. Draw the root (f (n)), branch into a children of size n/b (or whatever the recurrence specifies).
2. Identify the cost at each level: is it constant across levels, shrinking, or growing?
3. Identify the depth of the tree (balanced: solve n/b i = 1; unbalanced: bound shortest and longest
path separately).
4. Sum the per-level costs across all levels – use geometric series facts when costs shrink or grow
geometrically.
5. Don’t forget the leaf level separately if its cost pattern differs from internal levels.
6. The result is your guess – verify by substitution if a rigorous proof is required.
Three qualitative outcomes to recognize on sight
• Cost same at every level ⇒ total = (per-level cost) × (# levels)
• Cost shrinks geometrically going down ⇒ total = Θ(root cost)
• Cost grows geometrically going down ⇒ total = Θ(leaf-level cost)
CSE, IIT Kharagpur CS21203 Lecture 2: Recurrence & Substitution Method 17/19
Common Pitfalls in the Recursion Tree Method
1. Forgetting the leaf level has its own cost – often Θ(1) per leaf, but the number of
leaves can dominate everything else (a preview of what next lecture calls Case 1).
2. Sloppy depth computation – always solve “subproblem size = base case size” explicitly;
don’t eyeball it.
3. Assuming balance without checking – unequal splits need the shortest/longest path
sandwich (Example 3), not a single clean formula.
4. Geometric series sign errors – know by heart: ratio < 1 ⇒ sum is Θ(first term); ratio
> 1 ⇒ sum is Θ(last term); ratio = 1 ⇒ sum is (number of terms) × (common value).
5. Treating the tree’s output as a proof – it is a rigorous-feeling but informal derivation.
State the result as a guess unless you also verify it.
CSE, IIT Kharagpur CS21203 Lecture 2: Recurrence & Substitution Method 18/19
Recap and Looking Ahead
Key takeaways from today
1. The recursion tree turns a recurrence into a counting problem: levels × per-level cost,
summed.
2. Three qualitative tree shapes: level cost flat / shrinking / growing ↔ total is
(level)×(levels) / root / leaves.
3. Unbalanced trees need the shortest/longest-path sandwich, not a single depth formula.
4. The tree gives you a guess – substitution (Lecture 2) is how you’d make it rigorous.
Lecture 4 : The Master Theorem
For the common form T (n) = aT (n/b) + f (n), today’s three qualitative outcomes get
packaged into a direct two-line lookup – no tree required, once you know which of three cases
applies.
Questions?
CSE, IIT Kharagpur CS21203 Lecture 2: Recurrence & Substitution Method 19/19