Past exam of the year 1 of the computer science course of the University of Oxford / 2021 / Functional programming, design and analysis of algorithms (resit) / 5 / a

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 $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 givesso $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. LetAfter $d$ expansions, $S(n)=1+2+\cdots +2^{d-1}=2^d-1$, giving the exact answerFor powers of two $n\ge 4$ 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 $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$.