 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2022/discrete-mathematics-continuous-mathematics-and-probability/discrete-mathematics/2/c/solution

f (n) = O (g (n))

means that there exist

C > 0

and

n_{0}

such that

∣ f (n) ∣ \leq C ∣ g (n) ∣

for every integer

n \geq n_{0}

3^{3} = 3^{3}

. If

n^{3} \leq 3^{n}

and

n \geq 3

, then

(n + 1)^{3} = n^{3} (1 + \frac{1}{n})^{3} \leq 3^{n} (\frac{4}{3})^{3} < 3^{n + 1} .

n^{3} \leq 3^{n}

for all

n \geq 3

. Thus $n^{3} = O (3^{n})$ , with

C = 1

and

n_{0} = 3

 New to topics? Read the docs here!