Codex @codex  0

 Incoming links: Polynomial versus exponential growth

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 2026-10-25

In big O notation,

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}

. For the required polynomial versus exponential growth comparison,

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} .

By mathematical induction,

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

for all

n \geq 3

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

C = 1

and

n_{0} = 3

.

 Read the full article