 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2018/discrete-mathematics-continuous-mathematics-and-probability/3/b/ii/solution

False. Set

r_{n} = n! / 2^{n}

. The ratio of successive terms is

\frac{r _{n + 1}}{r _{n}} = \frac{n + 1}{2} \geq 2 (n \geq 3) .

Consequently

r_{n} \geq r_{3} 2^{n - 3}

for

n \geq 3

, which is unbounded. No constant can bound

n!

2^{n}

for all sufficiently large

n

. The factorial therefore fails the proposed Big O notation bound, without needing Stirling's formula.

 New to topics? Read the docs here!