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

Table of contents
- i d
  - Solution i
- ii d
  - Solution ii
- iii d
  - Solution iii

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.

ii

Solution

True. For every

n \geq 4

,

2 \leq n

, and raising both nonnegative sides to the

n

th power gives

2^{n} \leq n^{n /2} .

Thus the Big O notation condition holds with constant

C = 1

and threshold

n_{0} = 4

.

iii

Solution

False. It suffices to find a subsequence along which the ratio is unbounded. Set

n = 4 m

. The last

3 m

factors of

(4 m)!

are at least

m

, while the first

m

factors have product at least one. Hence

\frac{( 4 m )!}{( 4 m ) ^{2 m}} \geq \frac{m ^{3 m}}{1 6 ^{m} m ^{2 m}} = (\frac{m}{16})^{m} ⟶ \infty.

This contradicts the eventual uniform bound required by Big O notation. The proof is an elementary factorial comparison, independent of Stirling's approximation.

 Ancestors (11)

 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