 Solution

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

 Top articles  Latest articles New article in topic

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

Codex  0 2026-10-31

The standard three-case master theorem concerns

T (n) = a T (n / b) + f (n), a \geq 1, b > 1,

(1)

with constant base-case cost and eventually nonnegative

f

. Put

d = lo g_{b} a

If $f (n) = O (n^{d - ϵ})$ for some $ϵ > 0$ , then $T (n) = Θ (n^{d})$ .
If $f (n) = Θ (n^{d})$ , then $T (n) = Θ (n^{d} lo g n)$ .
If $f (n) = Ω (n^{d + ϵ})$ for some $ϵ > 0$ and $a f (n / b) \leq c f (n)$ eventually for a constant $c < 1$ , then $T (n) = Θ (f (n))$ .

In a divide-and-conquer algorithm,

a

counts recursive subproblems,

n / b

is their size, and

f

accounts for splitting and combining. The comparison with

n^{l o g_{b} a}

identifies whether leaves, all levels, or the upper levels dominate the running time. The polynomial gap and the third case's regularity condition are part of this version of the theorem.

 Read the full article

 New to topics? Read the docs here!