Exercises — Recursion tree method

• $a=4$ (four children), $b=2$ (size halves), $f(n)=n$.
• Depth: size at level $i$ is $n/2^i$; set $n/2^i=1\Rightarrow i={\log }_{2}n$. So ${\log }_{2}n$ levels (exactly integer since we assume $n=2^k$; otherwise $\lceil {\log }_{2}n\rceil$).
• Nodes at level $i$: $a^i=4^i$.
• Leaves: at the bottom level $i={\log }_{2}n$, count $=4^{{\log }_{2}n}=n^{{\log }_{2}4}=n^2$.

WHAT this looks like: a tree that gets very bushy — doubling the depth quadruples the width. That $n^2$ leaf count is a red flag that the leaves may dominate (we confirm this in L2).

• $a=1$, $b=2$, $f(n)=\Theta (1)$.
• Depth: ${\log }_{2}n$ (i.e. $\lceil {\log }_{2}n\rceil$ for general $n$).
• Nodes at level $i$: $1^i=1$. The "tree" is a single chain — one node per level.
• Leaves: $1^{{\log }_{2}n}=n^{{\log }_{2}1}=n^0=1$. Exactly one leaf.

WHAT this looks like: not a bush at all — a straight vertical stick ${\log }_{2}n$ nodes tall. Total work = ${\log }_{2}n$ nodes $\times \Theta (1)=\Theta (\log n)$.

Here $f(n)=n$ so $d=1$. Level-$i$ work: $W(i)=4^i\cdot \frac{n}{2^i}=n\cdot {\left(\frac{4}{2}\right)}^i=n\cdot 2^i.$ Ratio $r=a/b^d=4/2^1=2>1$ → increasing geometric series (the rising red curve in s01) → leaves dominate. By the verdict, the sum is $\Theta$ of its last term (level $L={\log }_{2}n$), and positivity of all terms makes that bound tight: $T(n)=\Theta \left(\text{leaf count}\right)=\Theta \left(n^{{\log }_{2}4}\right)=\boxed{\Theta (n^2)}.$ Cross-check with Master Theorem: $n^{{\log }_{b}a}=n^2$ vs $f(n)=n^1$; since $n^2$ grows faster, Case 1 → $\Theta (n^2)$. ✓

$a=2,b=2,f(n)=n^2$ so $d=2$. Level work: $W(i)=2^i{\left(\frac{n}{2^i}\right)}^2=2^i\cdot \frac{n^2}{4^i}=n^2{\left(\frac{2}{4}\right)}^i=n^2{\left(\frac{1}{2}\right)}^i.$ Ratio $r=1/2<1$ → decreasing (the falling black curve in s01) → root dominates. Sum $\le n^2\cdot \frac{1}{1-1/2}=2n^2$, and $\ge n^2$ (first term), so it is pinned: $T(n)=\boxed{\Theta (n^2)}.$ The root's $n^2$ sets the answer; everything below adds only a bounded fraction more.

$a=2,b=2,d=1$. Level work $=2^i(n/2^i)=n$ for every $i$ → ratio $r=2/2^1=1$ (the flat dashed curve in s01). Equal work $n$ per level $\times ({\log }_{2}n+1)$ levels: $T(n)=\boxed{\Theta (n\log n)}.$

$f(n)=n\log n$ is not a pure $n^d$, so the plain ratio rule doesn't apply. Compute level work honestly. At level $i$, subproblem size is $n/2^i$, so $W(i)=2^i\cdot \frac{n}{2^i}\log \frac{n}{2^i}=n(\log n-i).$ (We used $\log (n/2^i)=\log n-i\log 2=\log n-i$ in base 2.) Sum over levels $i=0$ to $L={\log }_{2}n$: $T(n)={\sum }_{i=0}^{{\log }_{2}n}n(\log n-i)=n{\sum }_{i=0}^{{\log }_{2}n}(\log n-i).$ The inner sum is $\log n+(\log n-1)+\cdots +1+0$ — the numbers from $0$ up to $\log n$, which total $\frac{\log n(\log n+1)}{2}=\Theta ({\log }^{2}n)$. Therefore $T(n)=\boxed{\Theta (n{\log }^{2}n)}.$ WHAT this looks like: per-level work decreases linearly (not geometrically) as we go down, so we can't just take the first term — we sum an arithmetic-style series, which gives the extra $\log$.

The two branches shrink at different rates, so there is no single $b$. We use the height range + per-level bound technique. (This is the same idea the parent note applies to $T(n/3)+T(2n/3)+n$: for a lopsided tree, cap the work summed across each level, then bracket the number of levels between the shortest and the longest root-to-leaf path.)

Look at the tree (figure below): at any level, the subproblem sizes add up to at most $n$ (since $\frac{n}{5}+\frac{4n}{5}=n$, and this stays $\le n$ deeper down). Because $f$ is linear, each level's total work is $\le n$.

• Shortest root-to-leaf path: always take the $\times \frac{1}{5}$ branch → size $n(\frac{1}{5}{)}^k=1$ → $k={\log }_{5}n$.
• Longest root-to-leaf path: always take the $\times \frac{4}{5}$ branch → size $n(\frac{4}{5}{)}^k=1$ → $k={\log }_{5/4}n$.

So height is between ${\log }_{5}n$ and ${\log }_{5/4}n$ — both are $\Theta (\log n)$ (they differ only by constant factors, since ${\log }_{c}n=\log n/\log c$). $n\cdot {\log }_{5}n\le T(n)\le n\cdot {\log }_{5/4}n\Rightarrow T(n)=\boxed{\Theta (n\log n)}.$

Size doesn't divide by a constant — it square-roots. The trick: figure out how many square-roots turn $n$ into $2$.

After $i$ square-roots, the size is $n^{1/2^i}$. Take ${\log }_2$ twice. Let $m={\log }_{2}n$. Then ${\log }_2(n^{1/2^i})=m/2^i$. We stop when the size reaches the base (${\log }_2$ of it $=1$), i.e. when $m/2^i=1\Rightarrow 2^i=m\Rightarrow i={\log }_{2}m={\log }_2{\log }_{2}n$.

The tree is a single chain (branching $a=1$), one node per level, each costing $1$. Total nodes = number of levels: $T(n)=\boxed{\Theta (\log \log n)}.$ WHAT this looks like: the substitution $m={\log }_{2}n$ converted "square-root each step" into "halve each step," which we already know gives $\log$. Applying $\log$ to the outside once more gives $\log \log n$. See Substitution Method.

$a=3,b=2,f(n)=n^2$ so $d=2$. Ratio: $r=\frac{a}{b^d}=\frac{3}{2^2}=\frac{3}{4}<1\Rightarrow \text{decreasing}\Rightarrow \text{root dominates}.$ Level work $=n^2(3/4{)}^i$; sum $\le n^2\cdot \frac{1}{1-3/4}=4n^2$. $T(n)=\boxed{\Theta (n^2)}.$ Sanity: leaf count is $n^{{\log }_{2}3}=n^{1.585}$, which is smaller than $n^2$, confirming the root (not the leaves) does the heavy lifting. See Divide and Conquer.

The flaw: they used $f(n)=n/\log n$ at every level, but $f$ must be evaluated at each level's size $n/2^i$, not at $n$.

Level-$i$ work (writing $L={\log }_{2}n$): $W(i)=2^i\cdot \frac{n/2^i}{\log (n/2^i)}=\frac{n}{\log n-i}.$ The denominator $\log n-i$ stays positive only while $i<{\log }_{2}n=L$; the last valid level is $i=L-1$ (below that the size hits the constant base case). So the precise summation range is $i=0,\dots ,L-1$: $T(n)={\sum }_{i=0}^{L-1}\frac{n}{\log n-i}\stackrel{k=\log n-i}{=}n{\sum }_{k=1}^L\frac{1}{k}=n\cdot H_L,$ where $H_m=1+\frac{1}{2}+\cdots +\frac{1}{m}$ is the harmonic number and $H_m=\Theta (\log m)$. With $L={\log }_{2}n$, $T(n)=n\cdot \Theta (\log L)=n\cdot \Theta (\log \log n)=\boxed{\Theta (n\log \log n)}.$ The classmate's $\Theta (n)$ under-counts: the per-level work actually grows as we descend (the denominator $\log n-i$ shrinks), and the harmonic sum contributes an extra $\log \log n$ factor.

• $T(n)=T(n)+1$: the subproblem is the same size $n$ ($b=1$ effectively). Setting size $=1$ gives $n/1^i=1$, which is never true for $n>1$ — the depth ${\log }_{1}n$ is undefined ($\log$ base $1$ doesn't exist). Every level adds $1$ more unit of work to a problem that never shrinks, so the tree is an infinite chain and the total diverges. No finite solution.
• $T(n)=T(n/1)+n$: dividing by $1$ leaves the size unchanged, so this is the same disease with $b=1$. Every level has size $n$ and costs $n$, giving an infinite chain of $n$'s that never bottoms out. The sum $n+n+n+\dots$ diverges → no finite solution.

LESSON: the recurrence $T(n)=aT(n/b)+f(n)$ requires $b>1$. If $b=1$ the problem doesn't shrink, the depth formula ${\log }_{b}n$ blows up, and the tree method (and Master Theorem) simply do not apply. Always check $b>1$ before drawing.

$a=4,b=2,d=2$. Ratio $r=a/b^d=4/2^2=1$. Balanced! Level work: $W(i)=4^i{\left(\frac{n}{2^i}\right)}^2=4^i\cdot \frac{n^2}{4^i}=n^2\text{ (every level)}.$ Equal work $n^2$ per level $\times \Theta (\log n)$ levels: $T(n)=\boxed{\Theta (n^2\log n)}.$ This is the "$a=b^d$" balanced case — same mechanism as merge sort, just with $n^2$ per level instead of $n$.