Is $3^{(2n)} = O(3^n)$ ? Why?

Question

Working on a Computer Science Fundamentals assignment and came across this. I see that I am supposed to find a $C$ for something... but that is about all i know. Can anyone break this down for me?

Thanks in advance.

Answer 1

Hint:

• Try to compute $\lim_{n \to \infty} \frac{3^{2n}}{3^n}$.
• Conclude if $\frac{3^{2n}}{3^n}$ is bounded by a constant.

Answer 2

$3^{2n}=\mathcal O(3^n)$ as $n\to \infty \iff \exists M: 3^{2n}\le M\cdot 3^n$ as $n\to \infty $.

$\frac{3^{2n}}{3^n}=3^n\to \infty$ as $n\to \infty$.

$\therefore \not \exists M: 3^{2n}\le M\cdot 3^n$ as $n\to \infty $.

So no.