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

Table of contents
- Solution 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.

 Ancestors (12)

 View article source

 Discussion (0)

There are no discussions about this article yet.

 Articles by others on the same topic (0)

There are currently no matching articles.

  See all articles in the same topic Create my own version