Exercises — Substitution method for recurrences

Just read off the pattern — no proof needed yet.

• (i) $a=3,b=4,h(n)=n^2$.
• (ii) $a=1,b=2,h(n)=1$.
• (iii) $a=4,b=2,h(n)=n$.

Why this matters: every later step plugs these three into the win-condition $h(n)\le cf(n)-acf(n/b)$. If you misread $a$ or $b$, every constant afterwards is wrong.

No. Induction requires reproducing the same constant $c$ you assumed. Ending at $(c+2)n$ means each level adds $2n$; over the $\log n$ levels this piles up to $\Theta (n\log n)$. A bound is only proven when the residual is $\le 0$ with a fixed $c$.

Guess: $T(n)\le cn\log n$. Assume (IH): $T(n/2)\le c\frac{n}{2}\log \frac{n}{2}$ (valid since $n/2<n$). Substitute: $T(n)\le 2\left(c\frac{n}{2}\log \frac{n}{2}\right)+n=cn\log \frac{n}{2}+n.$ Massage with the log split: $=cn(\log n-1)+n=cn\log n-cn+n=cn\log n-(c-1)n.$ Absorb: need $-(c-1)n\le 0\Rightarrow c\ge 1$. Base case at $n_0=2$: need $T(2)=3\le c\cdot 2\log 2=2c$. So $c\ge 1.5$. Combine: both conditions met by $c=1.5$ (rounded up: any $c\ge 1.5$). $✓$

So $T(n)\le 1.5n\log n$ for all $n\ge 2$. Same recurrence as Merge Sort Analysis.

Guess: $T(n)\le c\log n$. Assume: $T(n/2)\le c\log \frac{n}{2}=c(\log n-1)$. Substitute: $T(n)\le c(\log n-1)+1=c\log n-c+1.$ Absorb: residual $-c+1\le 0\Rightarrow c\ge 1$. Base case at $n_0=2$: $T(2)$ constant $\le c\log 2=c$; choose $c\ge \max (1,T(2))$. $✓$

Result: $T(n)=O(\log n)$ — the classic binary-search recurrence.

Guess: $T(n)\le cn$. Substitute: $T(n)\le 2\left(c\frac{n}{2}\right)+n=cn+n=(c+1)n.$ The residual is $+n>0$ — positive, and no choice of $c$ makes $+n\le 0$. The bound we reproduce is $(c+1)n$, not $cn$. Guess fails. True tight bound: $\Theta (n\log n)$ (proven in Exercise 2.1).

Substitute: $T(n)\le c\frac{n}{2}+c\frac{n}{4}+n=\frac{3}{4}cn+n.$ Absorb: need $\frac{3}{4}cn+n\le cn$, i.e. $n\le \frac{1}{4}cn$, i.e. $c\ge 4$. So $c=4$ works (residual $\frac{3}{4}\cdot 4n+n=3n+n=4n=cn$ exactly). $✓$ Result: $T(n)=O(n)$ with $c=4$.

Contrast with 3.1: here the coefficients $\frac{1}{2}+\frac{1}{4}=\frac{3}{4}<1$ leave shrinking room, so a plain constant absorbs the $+n$. In 3.1 the coefficient was $2\cdot \frac{1}{2}=1$, no room, so it failed.

Guess: $T(n)\le c{n}^2$. Substitute: $T(n)\le 4\left(c\right(\frac{n}{2}{)}^2)+n=4c\cdot \frac{n^2}{4}+n=c{n}^2+n.$ Absorb: residual $+n>0$ — plain $O(n^2)$ reproduces $c{n}^2+n$, not $c{n}^2$. Fails as-is! Fix (strengthen): guess $T(n)\le c{n}^2-dn$ (subtract lower-order term). Substitute the stronger guess: $T(n)\le 4(c\frac{n^2}{4}-d\frac{n}{2})+n=c{n}^2-2dn+n=c{n}^2-(2d-1)n.$ Absorb: need $-(2d-1)n\le -dn$, i.e. $(2d-1)\ge d$, i.e. $d\ge 1$. Pick $d=1$. Base case $n_0=1$: $T(1)=1\le c\cdot 1-1\cdot 1=c-1\Rightarrow c\ge 2$. Pick $c=2,d=1$: $T(n)\le 2n^2-n$ for $n\ge 1$, so $T(n)=O(n^2)$. $✓$

Why change variables? The $\sqrt{n}$ argument is ugly for induction (it doesn't shrink linearly). Substitute $m=\log n$ (so $n=2^m$, and $\sqrt{n}=2^{m/2}$). Let $S(m)=T(2^m)=T(n)$. Then $T(\sqrt{n})=T(2^{m/2})=S(m/2)$ and $\log n=m$: $S(m)=2S(m/2)+m.$ This is exactly the Exercise 2.1 recurrence! By that result: $S(m)=O(m\log m).$ Change back: $m=\log n$, so $T(n)=S(m)=O(m\log m)=O(\log n\cdot \log \log n).✓$ The trick: convert a multiplicative shrink ($\sqrt{n}$) into an additive halving via logs, then reuse a known result.

Guess: $T(n)\le c{n}^2$. Substitute: $T(n)\le 2\left(c\right(\frac{n}{2}{)}^2)+n^2=2c\cdot \frac{n^2}{4}+n^2=\frac{c}{2}{n}^2+n^2.$ Absorb: need $\frac{c}{2}{n}^2+n^2\le c{n}^2$, i.e. $n^2\le \frac{c}{2}{n}^2$, i.e. $c\ge 2$. Base case $n_0=1$: $T(1)=1\le c\cdot 1\Rightarrow c\ge 1$. Combine: $c=2$ satisfies both. So $T(n)\le 2n^2$, $T(n)=O(n^2)$. $✓$

Note: here $h(n)=n^2$ dominates the recursion cost, so the answer is $\Theta (n^2)$ — compare against Master Theorem Case 3.

Getting the guess (use Recursion Tree Method mentally): work per level multiplies by $3$ but problem size halves, so cost per level $=3^i\cdot (n/2^i)=n(3/2{)}^i$, growing geometrically → dominated by the leaves. Leaves: $3^{{\log }_{2}n}=n^{{\log }_{2}3}$. So guess $T(n)=\Theta (n^{{\log }_{2}3})$, and ${\log }_{2}3\approx 1.585$. Prove $O(n^{{\log }_{2}3})$. Let $\alpha ={\log }_{2}3$, so $3=2^{\alpha }$ and $3(n/2{)}^{\alpha }=3\cdot n^{\alpha }/2^{\alpha }=3n^{\alpha }/3=n^{\alpha }$. Plain guess $T(n)\le c{n}^{\alpha }$: $T(n)\le 3c(n/2{)}^{\alpha }+n=c{n}^{\alpha }+n.$ Residual $+n>0$ — fails. Strengthen: $T(n)\le c{n}^{\alpha }-dn$. $T(n)\le 3(c(n/2{)}^{\alpha }-d\frac{n}{2})+n=c{n}^{\alpha }-\frac{3d}{2}n+n=c{n}^{\alpha }-(\frac{3d}{2}-1)n.$ Absorb: need $-(\frac{3d}{2}-1)n\le -dn$, i.e. $\frac{3d}{2}-1\ge d$, i.e. $\frac{d}{2}\ge 1$, i.e. $d\ge 2$. Pick $d=2$. Base case $n_0=1$: $T(1)=1\le c\cdot 1-2\cdot 1=c-2\Rightarrow c\ge 3$. Pick $c=3,d=2$: $T(n)\le 3n^{\alpha }-2n$ with $\alpha ={\log }_{2}3$. So $T(n)=O(n^{{\log }_{2}3})$. $✓$

Why a separate proof? $O$ bounds from above ($\le$); $\Omega$ bounds from below ($\ge$). Together they give $\Theta$. The inequality direction flips, so the absorb condition flips too. Guess: $T(n)\ge cn\log n$ (want $c>0$). Assume: $T(n/2)\ge c\frac{n}{2}\log \frac{n}{2}$. Substitute: $T(n)\ge 2\left(c\frac{n}{2}\log \frac{n}{2}\right)+n=cn(\log n-1)+n=cn\log n-(c-1)n.$ Absorb (flipped): need $-(c-1)n\ge 0$, i.e. $c\le 1$. Base case $n_0=2$: $T(2)=1\ge c\cdot 2\log 2=2c\Rightarrow c\le 0.5$. Combine: pick $c=0.5$ (satisfies $c\le 1$ and $c\le 0.5$). So $T(n)\ge 0.5n\log n$, $T(n)=\Omega (n\log n)$. $✓$ Together with Exercise 2.1: $T(n)=\Theta (n\log n)$.