Worked examples — Recursion tree method

---

The scenario matrix

Every recurrence you can throw at a recursion tree lands in exactly one of these cells. The examples below are labelled with the cell they cover.

In cell C4 below, $\alpha$ and $\beta$ are just the two shrink fractions of an unbalanced split: one child gets a fraction $\alpha$ of the work (size $\alpha n$) and the other gets a fraction $\beta$ (size $\beta n$), with $0<\alpha ,\beta <1$. For instance $\alpha =\frac{1}{3},\beta =\frac{2}{3}$ in Ex 4.

#	Cell (scenario class)	Signature	Verdict	Example
C1	Ratio $r<1$ — decreasing levels	$a<b^d$	root wins: $\Theta (n^d)$	Ex 2, Ex 5
C2	Ratio $r=1$ — balanced levels	$a=b^d$	tie + $\log$: $\Theta (n^d\log n)$	Ex 1
C3	Ratio $r>1$ — increasing levels	$a>b^d$	leaves win: $\Theta (n^{{\log }_{b}a})$	Ex 3
C4	Unbalanced tree (two shrink fractions $\alpha ,\beta$)	$T(\alpha n)+T(\beta n)+f$	bound by height range	Ex 4
C5	Degenerate branching $a=1$	one child, no widening	chain, not a tree	Ex 5
C6	Subtract, don't divide	$T(n-c)+f(n)$	linear-depth tree	Ex 6
C7	Limiting / boundary $f$ tiny vs $\log$	$f(n)=\Theta (1)$	leaves or $\log$ edge case	Ex 7
C8	Real-world word problem	must extract $a,b,f$ from prose	any of above	Ex 8
C9	Exam twist — sneaky $b^d=a$ hidden	looks like C1/C3, is C2	catch the tie	Ex 9

Related tools you will see leaning on this: Master Theorem (the shortcut), Geometric Series (the summing engine), Big-O Notation (the bounding language), and Divide and Conquer (where these recurrences come from).

---

Worked Example 1 — Cell C2 (balanced): $T(n)=2T(n/2)+n$

Here $a=2$, $b=2$, $f(n)=n$ so $d=1$.

1. Compute the ratio $r=a/b^d$. $r=\frac{a}{b^d}=\frac{2}{2^1}=1.$ Why this step? $r$ tells us instantly whether we are in C1, C2, or C3 without drawing anything — it is the growth factor of the per-level work.
2. Read the picture: every level costs the same $n$. Level $i$ has $2^i$ nodes each of size $n/2^i$, so its work is $2^i\cdot (n/2^i)=n$. Look at the coral bars in the figure — they are all the same height. Why this step? $r=1$ literally means "next level's total = this level's total", so the work is a flat stack.
3. Count the levels. Size halves until it hits $1$: $n/2^i=1\Rightarrow i={\log }_{2}n$. Including level $0$ that is ${\log }_{2}n+1$ levels. Why this step? Total = (per-level work) $\times$ (number of levels) only when levels are equal.
4. Multiply. $T(n)=n\cdot ({\log }_{2}n+1)=\Theta (n\log n).$

---

Worked Example 2 — Cell C1 (root wins): $T(n)=3T(n/4)+n^2$

Here $a=3$, $b=4$, $f(n)=n^2$ so $d=2$.

1. Ratio. $r=a/b^d=3/4^2=3/16<1$. Why this step? $r<1$ is Cell C1 — the level sums form a decreasing geometric series.
2. Write the level sum. $W(i)=3^i(n/4^i{)}^2=n^2(3/16{)}^i$. Why this step? Confirms the ratio symbolically; the $(3/16{)}^i$ makes each level smaller than the last.
3. Sum the geometric series — and why the infinite bound is legal. The exact answer is the finite sum $n^2{\sum }_{i=0}^{{\log }_{4}n}(3/16{)}^i$. Because every term $(3/16{)}^i$ is positive, adding more terms only makes the sum larger; so the finite sum is $\le$ the infinite sum: ${\sum }_{i=0}^{{\log }_{4}n}{\left(\frac{3}{16}\right)}^i\le {\sum }_{i=0}^{\infty }{\left(\frac{3}{16}\right)}^i=\frac{1}{1-3/16}=\frac{16}{13}.$ Since the sum is also $\ge$ its first term $1$, we get $1\le \text{sum}\le \frac{16}{13}$ — trapped between two constants. So $T(n)$ is $\Theta (n^2)$. Why this step? Replacing a finite sum by the infinite one is only valid when terms are positive (so the infinite sum is a genuine upper bound) and the ratio is $<1$ (so that upper bound is finite). Both hold here.
4. Verdict. $T(n)=\Theta (n^2)$. The root dominates.

---

Worked Example 3 — Cell C3 (leaves win): $T(n)=4T(n/2)+n$

Here $a=4$, $b=2$, $f(n)=n$ so $d=1$.

1. Ratio. $r=a/b^d=4/2^1=2>1$. Why this step? $r>1$ is Cell C3 — level sums grow going down; the bottom is fattest.
2. Level sum. $W(i)=4^i(n/2^i)=n\cdot 2^i$. Look at the figure: bars double each level. Why this step? Confirms growth; now the last term dominates, not the first.
3. Sum an increasing geometric series. Its total is dominated by its last term. Number of levels $={\log }_{2}n$, so the last level's work is $n\cdot 2^{{\log }_{2}n}=n\cdot n=n^2$. $T(n)=n{\sum }_{i=0}^{{\log }_{2}n}{2}^i=n(2^{{\log }_{2}n+1}-1)=\Theta (n^2).$ Why this step? For $r>1$, sum $\approx$ last term, which equals the leaf cost $n^{{\log }_{b}a}$.
4. Verdict. Leaves count $=a^{{\log }_{b}n}=4^{{\log }_{2}n}=n^{{\log }_{2}4}=n^2$. So $T(n)=\Theta (n^2)$, leaves win.

---

Worked Example 4 — Cell C4 (unbalanced): $T(n)=T(n/3)+T(2n/3)+n$

1. Per-level work — upper bound. At each full level the child sizes sum to at most the parent size, because $\frac{n}{3}+\frac{2n}{3}=n$. Since $f$ is linear, the sum of costs across that level is $\le n$. Why this step? When $f$ is linear, "sum of sizes" $=$ "sum of costs", so lopsidedness doesn't change the per-level total — it stays capped at $n$.
2. Per-level work — lower bound (near the top). For the first ${\log }_{3}n$ levels the fast branch has not yet bottomed out, so all subproblems on that level are still alive and their sizes still add up to exactly $n$. Hence each of those top ${\log }_{3}n$ levels costs $\ge$ (a constant times) $n$ too. So per level the work is $\Theta (n)$ for those levels, not merely $\le n$. Why this step? Without a lower bound we could only prove $T(n)=O(n\log n)$; to also get $T(n)=\Omega (n\log n)$ we must show many levels each genuinely cost about $n$.
3. Shortest path (fastest shrink). Follow the $/3$ branch: $n/3^k=1\Rightarrow k={\log }_{3}n$. This is the shallow side. Why this step? Gives a lower bound on total depth, and (with step 2) at least ${\log }_{3}n$ full-cost levels.
4. Longest path (slowest shrink). Follow the $\times 2/3$ branch: $n(2/3{)}^k=1\Rightarrow k={\log }_{3/2}n$. This is the deep side (see the long butter-colored path in the figure). Why this step? Gives an upper bound on depth; the deepest path sets the tree height.
5. Combine. Total is at least $n\cdot {\log }_{3}n$ (step 2: ${\log }_{3}n$ levels each costing $\ge$ about $n$) and at most $n\cdot {\log }_{3/2}n$ (step 1: $\le {\log }_{3/2}n$ levels each costing $\le n$). All these logs differ only by constant factors (${\log }_{3}n=\frac{{\log }_{2}n}{{\log }_{2}3}$, etc.), so both bounds are in the class $\Theta (n\log n)$: $n{\log }_{3}n\le T(n)\le n{\log }_{3/2}n\Rightarrow T(n)=\Theta (n\log n).$ Why this step? An upper bound alone gives $O$; a lower bound alone gives $\Omega$; squeezing between two bounds of the same $\Theta$ class is exactly what proves the tight $\Theta (n\log n)$. Steps 1–2 supplied the per-level costs, steps 3–4 supplied the two level counts, and here we multiply and combine.

---

Worked Example 5 — Cell C1 & C5 (single child): $T(n)=T(n/2)+n$

Here $a=1$, $b=2$, $f(n)=n$ so $d=1$.

1. Ratio. $r=a/b^d=1/2<1$. Cell C1 (and C5, since $a=1$ means no widening — a straight line of nodes). Why this step? $a=1$ collapses the tree to a chain; the sum is still geometric.
2. Level sum. $W(i)=1^i\cdot (n/2^i)=n/2^i$. Why this step? Each node is alone, so per-level work is just the single node's cost, halving each step.
3. Sum. $T(n)=n{\sum }_{i=0}^{{\log }_{2}n}(1/2{)}^i\le n\cdot \frac{1}{1-1/2}=2n=\Theta (n)$. Why this step? Decreasing geometric → bounded by twice the first term.
4. Verdict. $T(n)=\Theta (n)$. Root (the $+n$) dominates.

---

Worked Example 6 — Cell C6 (subtract, not divide): $T(n)=T(n-1)+n$

1. Height. Size drops $n\to n-1\to n-2\to \cdots \to 1$. That is $n$ levels — linear depth, not log. Why this step? Subtraction gives a long thin chain; there is no $b$ to take a log with.
2. Per-level work. One node per level (branching $a=1$), of size $n-i$, costing $n-i$. Why this step? Establishes each row's contribution.
3. Sum. Add every level's cost: $T(n)={\sum }_{i=0}^{n-1}(n-i)=n+(n-1)+\cdots +2+1=\frac{n(n+1)}{2}.$ Why this step? This is an arithmetic (not geometric) series — the classic $1+2+\cdots +n$ triangle; its closed form is $\frac{n(n+1)}{2}$.
4. Verdict. $\frac{n(n+1)}{2}=\frac{1}{2}{n}^2+\frac{1}{2}n$, whose top-order term is $n^2$, so $T(n)=\Theta (n^2).$ The Master Theorem does not apply here (it needs division); the tree method still works.

---

Worked Example 7 — Cell C7 (limiting, tiny $f$): $T(n)=2T(n/2)+1$

Here $a=2$, $b=2$, $f(n)=1$ so $d=0$.

1. Ratio. $r=a/b^d=2/2^0=2>1$. A limiting case: the local work is so tiny ($d=0$) that branching always wins. Why this step? Constant $f$ ($d=0$) makes $b^d=b^0=1$, so $r=a>1$ automatically — the boundary where $f$ is as small as it can be.
2. Level sum. $W(i)=2^i\cdot 1=2^i$ — pure doubling, driven only by node count. Why this step? With no size-dependent work, cost = number of nodes.
3. Sum. $T(n)={\sum }_{i=0}^{{\log }_{2}n}{2}^i=2^{{\log }_{2}n+1}-1=2n-1=\Theta (n)$. Why this step? Geometric with $r=2$; total $\approx$ last term = leaf count.
4. Verdict. $T(n)=\Theta (n)$. Leaves win; total = number of nodes $\approx 2n$.

---

Worked Example 8 — Cell C8 (real-world word problem)

1. Extract $a,b,f$. "three sub-piles" → $a=3$; "size $n/3$" → $b=3$; "scan the whole pile once, $n$ steps" → $f(n)=n$, so $d=1$. Why this step? Turn prose into the three knobs before any math.
2. Ratio. $r=a/b^d=3/3^1=1$. Cell C2 (balanced). Why this step? Ties the word problem to a matrix cell.
3. Per-level & depth. Each level costs $3^i(n/3^i)=n$. The size hits $1$ when $n/3^i=1\Rightarrow i={\log }_{3}n$, and counting the root level $0$ as well gives ${\log }_{3}n+1$ levels. Why this step? Balanced levels → total = per-level × levels, so we need the exact level count including the top row (the "$+1$" for level $0$).
4. Total. $T(n)=n\cdot ({\log }_{3}n+1)=\Theta (n\log n)$. Why this step? Because step 2 showed every level costs the same $n$ (the $r=1$ flat-stack case), the total is simply (per-level cost $n$) $\times$ (number of levels ${\log }_{3}n+1$); the constant $+1$ and the base of the log are swallowed by $\Theta$ (a base change is only a constant factor).

---

Worked Example 9 — Cell C9 (exam twist, hidden tie): $T(n)=2T(n/4)+\sqrt{n}$

Here $a=2$, $b=4$, and $f(n)=\sqrt{n}=n^{1/2}$ so $d=\frac{1}{2}$.

1. Rewrite $f$ as a clean power. $\sqrt{n}=n^{1/2}$, so $d=\frac{1}{2}$. Why this step? You cannot compute the ratio $r=a/b^d$ until the local work is written as $n^d$; leaving it as "$\sqrt{n}$" hides the exponent and invites the trap.
2. Compute $b^d$ honestly — this is where the trap lives. $b^d=4^{1/2}=2$, which is exactly $a$. So $r=\frac{a}{b^d}=\frac{2}{2}=1.$ Why this step? The reflex is to eyeball "small $f$, big shrink → root wins (C1)". But $4^{1/2}=2$ equals $a$, making $r=1$ a tie (C2), not a root case. Doing the exponent by hand is the only safeguard.
3. Confirm the tie by direct cancellation. Level $i$ has $2^i$ nodes each of size $n/4^i$, so its work is $W(i)=2^i{\left(\frac{n}{4^i}\right)}^{1/2}=2^i\cdot \frac{n^{1/2}}{2^i}=n^{1/2}.$ The $2^i$ cancels — every level costs the same $\sqrt{n}$, the flat-stack signature of $r=1$. Why this step? Re-deriving the per-level work from scratch double-checks the ratio verdict; if the $2^i$ had not cancelled, we'd know we mislabelled the cell.
4. Count levels and multiply. Size hits $1$ at $n/4^i=1\Rightarrow i={\log }_{4}n$; including level $0$ that is ${\log }_{4}n+1$ levels. Since levels are equal, $T(n)=n^{1/2}\cdot ({\log }_{4}n+1)=\Theta (\sqrt{n}\log n).$ Why this step? Balanced levels mean total = (per-level cost $\sqrt{n}$) $\times$ (number of levels); the $+1$ and the log base vanish inside $\Theta$.

---

Recall Master checklist for ANY recurrence

Compute $r=a/b^d$ (or find the height if there's no clean $b$): Cell C1 ($r<1$) ::: Root wins, $\Theta (n^d)$ — decreasing geometric. Cell C2 ($r=1$) ::: Balanced, $\Theta (n^d\log n)$ — flat levels. Cell C3 ($r>1$) ::: Leaves win, $\Theta (n^{{\log }_{b}a})$ — increasing geometric. Cell C4 (two shrink rates $\alpha ,\beta$) ::: Bound by height range $[{\log }_{1/\text{fast}}n,{\log }_{1/\text{slow}}n]$. Cell C6 (subtract $c$) ::: Linear depth, use arithmetic series, Master Theorem does NOT apply.

---

Connections

• Parent: Recursion Tree Method — the machine these examples run.
• Master Theorem — the shortcut whose three cases are exactly C1/C2/C3.
• Geometric Series — the summing engine behind every ratio verdict.
• Substitution Method — an alternative to confirm these answers by guess-and-prove.
• Divide and Conquer · Merge Sort · Binary Search — where these recurrences are born.
• Big-O Notation — the $\Theta$ language of every verdict.