Prove that $f(n)=n^2+2^n$ is $\cal{O}(g(n))$, where $g(n)=3^n$

Question

Prove that $f(n)$ is $\cal{O}(g(n))$, where $$f(n)=n^2+2^n$$ $$g(n)=3^n$$

I tried finding the limit using l'Hôpital's rule and breaking it into parts but it got too complicated.

Answer 1

$f(n) \in O(g(n))$ if there is a constant $M>0$ such that $f(n) \leq M g(n)$ for every sufficiently large $n$. So, we are looking for a constant $M$ such that $n^2+2^n \leq M3^n$ for every sufficiently large $n$. We observe that for $n\geq 4$, we have $n^2 \leq 2^n$, and therefore when $n \geq 4$, $n^2+2^n \leq 2^n + 2^n = 2\times 2^n \leq 2\times 3^n$. Hence, when $n \geq 4$, $f(n) \leq 2 g(n)$, and thus $f(n)\in O(g(n))$.

Answer 2

You can consider $$\lim_{n\rightarrow\infty} \frac{n^2 + 2^n}{3^n} = \lim_{n\rightarrow\infty} \frac{n^2}{3^n} + \lim_{n\rightarrow\infty} \bigg(\frac{2}{3}\bigg)^n.$$ Clearly both of the limits on the right hand side go to $0$ which shows that $f(n)$ is $o(g(n))$ which is stronger than just $f(n)$ being $\mathcal{O}(g(n))$. So in fact $f(n)$ is $\mathcal{O}(g(n))$.