Prove that $3^n=O(n^3) $ is not true

Question

Prove that $3^n=O(n^3) $ is not true. I came up to $3^n \le cn^3 $ but can not go further, I guess I need to do log both side, But don't know

If you start that way, then note your goal is to derive a contradiction. Taking logarithms is not a terrible idea to start with. Have you taken calculus? Try taking a limit of something. — , Mar 03 '14 at 03:43

score 1 · Accepted Answer · answered Mar 03 '14 at 03:46

1

$$\lim_{n\to\infty}\sup\frac{3^n}{n^3} = \lim_{n\to\infty}\frac{3^n}{n^3} = \infty$$ by l'Hopital's

http://en.wikipedia.org/wiki/Big_O_notation#Formal_definition

answered Mar 03 '14 at 03:46

Flowers

775
4
13

score 1 · Answer 2 · answered Mar 03 '14 at 03:53

Well, $$ 3^n > e^n = \lim_{k\to\infty} \left(1+\frac{n}{k}\right)^k > \left(1+\frac{n}{4}\right)^4 = \frac{n^4}{4^4} + O(n^3). $$

Thus, $3^n$ could not be $O(n^3)$, since it is at least $O(n^4)$.

Recall that $f(x)=O(g(x))$ if $\lim_{x\to C} \frac{f(x)}{g(x)} = L \neq 0$. So, another way would be to consider $$ \lim_{n\to\infty} \frac{n^3}{3^n} $$ Using your favorite method (or a line of argument similar to my above one), you can show that this limit goes to 0.

Prove that $3^n=O(n^3) $ is not true

2 Answers2