 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2019/discrete-mathematics-continuous-mathematics-and-probability/3/d/i/solution

False. For

n \geq 3

, every factor from

3

through

n

is at least

3

, so

n! \geq 2 \cdot 3^{n - 2}, \frac{n !}{2 ^{n}} \geq \frac{2}{9} (\frac{3}{2})^{n} ⟶ \infty.

No fixed multiple of

2^{n}

eventually bounds the factorial, contradicting the definition of Big O notation. No use of Stirling's approximation is required.

 New to topics? Read the docs here!