 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-resit/2/c/ii/solution

False. Put

r_{n} = 3^{n} / n^{3}

for

n \geq 1

. For

n \geq 4

\frac{r _{n + 1}}{r _{n}} = 3 (\frac{n}{n + 1})^{3} \geq 3 (\frac{4}{5})^{3} = \frac{192}{125} > 1.

Thus

r_{n} \geq r_{4} (192/125)^{n - 4} \to \infty

. No fixed constant can bound

3^{n} / n^{3}

eventually, so

3^{n} \neq = O (n^{3})

. This is an explicit comparison of exponential growth with polynomial growth.

 New to topics? Read the docs here!