Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Functional programming, design and analysis of algorithms / 5 / c / Solution

Put $\alpha ={\log }_{b}a$. With a nonnegative toll bounded by $O(n^d)$, the Master theorem gives the upper boundsIf the base cost is $\Theta (1)$ and the toll is $\Theta (n^d)$, these become the usual tight $\Theta$ bounds. The printed $O$ toll by itself does not imply those lower bounds; for example, the toll could vanish.

For the two requested proofs, let $n=b^k$ as permitted. Expanding the recurrence relation through $k$ levels givesWhen $d=\alpha$, the ratio is one. The sum has $k={\log }_{b}n$ terms, so $T(n)=O(n^d\log n)$. With matching positive lower bounds on each level's work, the same expansion gives $\Theta (n^d\log n)$.

When $d>\alpha$, the ratio $r=a/b^d$ is strictly below one. The geometric series is at most $1/(1-r)$, so the internal work is $O(n^d)$; the leaf term $O(n^{\alpha })$ is also $O(n^d)$. A $\Theta (n^d)$ root toll supplies the matching lower bound in the tight version. This proves both requested cases.

There is a small termination qualification in the printed generality: if $1<b<2$, the literal base case only at $n=1$ may leave ceil(n/b) = n at a small integer, for example $n=2,b=3/2$. The standard rounded Master theorem assumes a sufficiently large fixed base-case cutoff so that recursive sizes decrease. The allowed unrounded powers-of-$b$ proof above does not use that problematic rounded step. Also, a literal number of recursive calls is integral, though the algebraic recurrence expansion remains meaningful for positive real $a$.