 Solution

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

The exponential function eventually grows faster than the fixed polynomial. A direct justification uses the ratio

r_{n} = 4^{n} / n^{4}

\frac{r _{n + 1}}{r _{n}} = 4 (\frac{n}{n + 1})^{4} ⟶ 4.

For all sufficiently large

n

, this ratio exceeds

2

, so

r_{n}

grows without bound. The proposed Big O notation bound is therefore impossible:

False: 4^{n} \neq = O (n^{4}) .

 New to topics? Read the docs here!