1.2.2 The recursion-tree method · GATE 2027 Algorithms

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

T(n) = 2T(n − 1) + 1, T(0) = 0: closed form? from Lesson 1.2.1
Θ of a loop where j doubles up to i, inside i = 1..n? from Lesson 1.1.3
1 + 1/2 + 1/4 + … converges to? from Lesson 0.1.2

1 · The Hook

🎣

Unrolling 3T(n/4) + n² by algebra is painful. Drawing it is easy: a tree whose root costs n², whose 3 children cost (n/4)² each, and so on. Add up each level, then add the levels. Whether the sum is dominated by the top, spread evenly, or dominated by the leaves tells you the answer.

2 · Predict First

🤔

T(n) = 2T(n/2) + n. Draw the tree: the root does n work; 2 children do n/2 each; 4 grandchildren n/4 each … What does each level cost in total, and how many levels are there?

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

Every level costs n (2ⁱ nodes × n/2ⁱ). There are log n + 1 levels. Total Θ(n log n).

Building the tree for T(n) = a·T(n/b) + f(n)

Level i has aⁱ nodes, each on a problem of size n/bⁱ, each costing f(n/bⁱ).
Level cost = aⁱ · f(n/bⁱ).
Depth: problems reach size 1 at level log_b n.
Leaves: a^(log_b n) = n^(log_b a) (swap rule, Lesson 0.1.2), each Θ(1).

Three shapes of the sum

Level costs shrink geometrically (top-heavy): the root dominates → Θ(f(n)). 3T(n/4) + n²: level i costs (3/16)ⁱ n² → Θ(n²).
Level costs equal: (cost per level) × (number of levels) → Θ(f(n) log n). 2T(n/2) + n → Θ(n log n).
Level costs grow geometrically (bottom-heavy): the leaves dominate → Θ(n^(log_b a)). 4T(n/2) + n: level i costs 2ⁱ·n → leaves n² → Θ(n²).

Unequal splits

T(n) = T(n/3) + T(2n/3) + n: every full level costs n; the longest path shrinks by 2/3 each step, so depth = log_{3/2} n → Θ(n log n). T(n) = T(n/2) + T(n/4) + n: level costs n, 3n/4, 9n/16 … (fractions add to 3/4 < 1) → geometric decrease → Θ(n).

4 · Visual

T(n) = 3T(n/4) + n^2

level 0:            n^2                              cost n^2
level 1:   (n/4)^2  (n/4)^2  (n/4)^2                 cost (3/16) n^2
level 2:   9 nodes of (n/16)^2                       cost (3/16)^2 n^2
...                                                  geometric, ratio 3/16 < 1
leaves: 3^(log4 n) = n^0.79                          -> total Theta(n^2)

Recurrence	Level i cost	Shape	Answer
2T(n/2) + n	n	equal	n log n
3T(n/4) + n²	(3/16)ⁱ n²	shrinking	n²
4T(n/2) + n	2ⁱ n	growing	n²
2T(n/2) + 1	2ⁱ	growing	n

5 · Worked Examples

Example 1 Easy

How many leaves does the recursion tree of T(n) = 8T(n/2) + n² have?

Solution

8^(log n) = n^(log 8) = n³.

Example 2 Medium

Solve T(n) = 2T(n/2) + 1 with the tree.

Solution

Level i costs 2ⁱ (growing); leaves n → Θ(n).

Example 3 GATE

Solve T(n) = T(n/5) + T(4n/5) + n.

Solution

Each full level costs n; depth log_{5/4} n → Θ(n log n).

6 · GATE Traps

⚠️

Leaves number n^(log_b a), not n.
Equal levels give an extra log n factor.
With unequal splits, check whether the fractions add to 1 (n log n) or less (n).
The deepest path sets the depth with unequal splits.

7 · Memory Hook

🧠

"Top-heavy: root wins. Balanced: times log n. Bottom-heavy: leaves win."

8 · Connect the Dots

The recursion tree shows why; the master theorem (next lesson) packages the three shapes into a lookup rule for a·T(n/b) + f(n).

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1MCQ1 markTree shape

T(n) = 2T(n/2) + n². The recursion tree is:

(A) balanced, Θ(n log n)
(B) top-heavy, Θ(n²)
(C) bottom-heavy, Θ(n)
(D) balanced, Θ(n² log n)

Q2NAT1 markLeaves

Number of leaves (as a power of n) in the tree of T(n) = 9T(n/3) + n: n^k, k = ?

Numerical answer: ________

Q3MCQ1 markUnequal split

T(n) = T(n/2) + T(n/3) + n is:

(A) Θ(n)
(B) Θ(n²)
(C) Θ(n log n)
(D) Θ(log n)

Q4MCQ1 markBottom-heavy

T(n) = 3T(n/2) + n is:

(A) Θ(n log n)
(B) Θ(n)
(C) Θ(n^(log 3))
(D) Θ(n²)

Q5NAT2 marksLevel cost

In the tree of T(n) = 4T(n/2) + n, what is the total cost of level 3 when n = 64?

Numerical answer: ________

10 · Rule Card

Level i: aⁱ nodes of size n/bⁱ; cost aⁱ·f(n/bⁱ); depth log_b n; leaves n^(log_b a).
Shrinking levels → Θ(f(n)); equal → Θ(f(n) log n); growing → Θ(n^(log_b a)).
Unequal splits: fractions sum to 1 → n log n; less than 1 → n (for f = n).

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

recursion treelevel costtree depth log_b nnumber of leaves n^(log_b a)top-heavy, balanced, bottom-heavy sumsunequal splits

12 · Answer Vault

Answer Vault

Try the questions first. Open when you are ready to check.

Recall Warm-up

2ⁿ − 1.
Θ(n log n).
2 (a constant).