Good evening,

I have a question about section 7.

How can I prove that: n^700 = O(2^n) ??

It seems very obvious, but can I prove it only with the definition of O ??

Thanks in advance,

Almog

Your question is a special case of the following (assuming you know that n^{100}/2^n \to 0):

Consider two functions f,g: R^+ \rightarrow R^+.

- Suppose that \lim_{n\to\infty} \frac{f(n)}{g(n)} = 0. Prove that f=O(g).
- Suppose that \limsup_{n\to\infty} \frac{f(n)}{g(n)} \leq c (where c is a constant). Prove that f=O(g).

Yes, I know that the limit is 0.

I thought I can prove n^700 = O(2^n) without relying on this known limit, but only with the definitin of O.

Never mind, thank you.