 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2017/functional-programming-design-and-analysis-of-algorithms/5/c/solution

For fixed

a \geq 1

b > 1

and

d \geq 0

, a version of the Master theorem states that, with bounded positive base costs,

T (n) = a T (n / b) + Θ (n^{d}), p = lo g_{b} a ⟹ T (n) = ⎩ ⎨ ⎧ Θ (n^{p}), Θ (n^{p} lo g n), Θ (n^{d}), d < p, d = p, d > p .

Usual floors and ceilings preserve these bounds when a sufficiently large constant-size base case ensures strict size decrease.

$A$ : $T_{A} (n) = 3 T_{A} (⌈ 2 n /3 ⌉) + Θ (1)$ , hence $O (n^{l o g_{3/2} 3})$ , with exponent approximately $2.7095$ . Base cases must include $n \leq 2$ because the ceiling otherwise need not decrease.
$B$ : $T_{B} (n) = 9 T_{B} (⌈ n /3 ⌉) + O (n^{2})$ , hence $O (n^{2} lo g n)$ by comparison with the equality recurrence having $Θ (n^{2})$ overhead. If that overhead is actually quadratic this is also tight; the stated upper bound alone does not establish a matching lower bound.
$C$ : $T_{C} (n) = 3 T_{C} (n - 1) + Θ (1)$ , whose expansion is a geometric series, hence $O (3^{n})$ , in fact $Θ (3^{n})$ for nonzero base costs. The divide-by-a-constant Master theorem does not apply to a decrement by one.

$B$ is asymptotically fastest; $C$ is slowest. Even the quadratic-logarithmic upper bound for

B

is smaller than the tight polynomial order of

A

 New to topics? Read the docs here!