Big-Oh and limits proof?

Question

Prove or disprove: $2^n$ is in $O(3^n)$. I know I have to use some calculus limit techniques but I can't seem to get anywhere. Steps and an approach would be helpful, especially confirming if this has to be disproved or not

Answer 1

Apply the same techniques I've shown you in your other threads:

$$L = \lim_{n \to \infty} \frac{2^{n}}{3^{n}} = \lim_{n \to \infty} (\frac{2}{3})^{n} = 0$$

So $3^{n}$ strictly dominates $2^{n}$, and $L = 0$ implies your result.

Check out this tutorial on complexity for more on the limit test and your calculus techniques: http://www.dreamincode.net/forums/topic/321402-introduction-to-computational-complexity/

Answer 2

First I imagine that $n$ is an integer and that you want to study this problem when $n$ goes to $+\infty$. That's probably obvious but better to be sure!

Then please write the definition of $2^n = O(3^n)$.

That should be something like there exists $C>0$ real and $N$ integer such that for $n > N$ you have $|2^n| \le C|3^n|$.

Now what do you think of $2^n \le 3^n$? And how then can you conclude?