= Solution
There are three unnumbered cases inside this leaf.
For the nine-child recurrence, a <recursion> tree has $9^j$ subproblems of size about $n/3^j$. There are $\Theta(n^2)$ constant-size leaves, and the total unit work over earlier levels is a geometric sum of the same order. Hence \b[$T(n)=\Theta(n^2)$]. This is also the first case of the <master theorem>, since $\log_3 9=2$ and the additive work is constant.
For the decrementing recurrence, summing from the supplied base at three gives
$$
T(n)=1+\sum_{j=4}^{n}j=\frac{n(n+1)}2-5\quad(n\geq3),
$$
so \b[$T(n)=\Theta(n^2)$] here as well. Values at the smaller base indices remain one as specified.
For the recurrence that squares its recursive result, <set> $S(n)=\log_2 T(n)$. Then $S(n)=1+2S(\lfloor n/2\rfloor)$ above the base range. Let
$$
d(n)=\min\{j\geq0:\lfloor n/2^j\rfloor\leq3\}=\max(0,\lfloor\log_2 n\rfloor-1)\quad(n\geq1).
$$
After $d$ expansions, $S(n)=1+2+\cdots+2^{d-1}=2^d-1$, giving the exact answer
$$
\boxed{T(n)=2^{\,2^{d(n)}-1}.}
$$
For powers of two $n\geq4$ this is $2^{n/2-1}$. For arbitrary <positive integer> $n$, the exact values form plateaux: $T(4)=\cdots=T(7)=2$, while $T(8)=\cdots=T(15)=8$. In general \b[$T(n)=2^{\Theta(n)}$]. It is not $\Theta(2^{n/2})$ uniformly over <integer> $n$: near the top of a plateau the exponent is closer to $n/4$. Keeping the <integer> halving is essential; the ordinary linear <master theorem> does not apply to squaring $T$.
Back to article page
