Which one is asymptotically larger: $n 2^n$ or $3^n$? Which of the following functions is larger asymptotically: $n 2^n$ or $3^n$?
If I take $\log$ on both functions and then compare, I am getting $n 2^n$ as larger, but the answer given is $3^n$. Where am I going wrong?
$n 2^n$ vs. $3^n$ is equivalent to comparing $\log(n 2^n)$ vs. $\log 3^n$, or $\log_2 n +n$ vs. $n \log_2 3$, now how do I proceed?
 A: Consider $\displaystyle f(x)=\sum_{n=0}^{\infty} x^n=\frac{1}{1-x}$ for $|x|<1$.
Then $\displaystyle xf'(x)=\sum_{n=0}^{\infty} nx^n$.
Taking $x=\dfrac{2}{3}$ we see that the series for $xf'(x)$ converges and so
$$
\lim_{n\to\infty}\dfrac{n 2^n}{3^n}=0
$$
This means that $3^n$ is asymptotically larger than $n2^n$.
By considering higher derivatives, we see that $3^n$ is asymptotically larger than $n^k2^n$ and so is asymptotically larger than $p(n)2^n$ for every polynomial $p$.
A: Let's consider $\dfrac {3^n}  {n 2^n}$:
$$\frac {3^n} {n 2^n} = {\rm e} ^{\log \frac {3^n} {n 2^n}} = {\rm e} ^{\log 3^n - \log (n 2^n)} .$$
Now
$$\log (3^n) - \log (n 2^n) = n \log 3 - \log n - n \log 2 =  n \left( \log 3 - \log 2  - \frac {\log n} n \right)$$
and
$$\lim \limits _{n \to \infty} \frac {\log n} n = 0, \quad \log 3 - \log 2 > 0 ,$$
so
$$\lim \limits _{n\to \infty} \frac {3^n}  {n 2^n} = \infty .$$
A: On expanding Binomially,
$3^n = (2+1)^n = {{n} \choose {0}} \cdot 2^n + {{n} \choose {1}} \cdot 2^{n-1} + \cdot \cdot \cdot$
So,
$3^n > n \cdot 2^{n-1} \approx n \cdot 2^n \cdot \frac{1}{2} \approx n \cdot 2^n $
Because Constants don't matter in Assymptotic comparisons.
So,
$$3^n > n \cdot 2^n$$
