1

I'm trying to compare $f(n) = 3^n$ and $g(n) = n\cdot2^n$ to determine whether $f \in O(g)$, $f \in \Omega(g)$, or $f \in \Theta(g)$.

My gut is telling me that $g(n) = n\cdot2^n$ grows faster, and so $f \in O(g)$, but I'm having a hard time coming up with a rigorous argument. I've tried using limits but keep getting things like $0 \cdot \infty$.

Can anyone lend a helping hand?

Kakarot_7
  • 151
Ryan
  • 311
  • 1
    Hmm. Try plugging in $n=1000$. Then $$f(1000)=3^{1000}=10^{1000\log_{10}3}\approx10^{477}.$$ But $$g(1000)=1000\cdot 2^{1000}=10^3\cdot10^{1000\log_{10}2} \approx 10^3\cdot10^{301}=10^{304}.$$ So for that value of $n$ $f$ is larger by 173 orders of magnitude. As is fitting, here $\approx$ refers to the exponent. Who cares about the most significant digit anyway :-) – Jyrki Lahtonen Jan 30 '15 at 09:18
  • 1
    IOW, your gut feeling is a bit underdeveloped. Play with the calculator! – Jyrki Lahtonen Jan 30 '15 at 09:21
  • 1
    Having played with the problem numerically, I now understand that $f \in \Omega(g)$. However, I don't really have an intuition for this, and am unable to give a formal argument. Can anyone help me with that? – Ryan Jan 30 '15 at 09:25
  • 1
    Mind you, calculator games can also mislead. If you compare the growth of $1.01^n$ and $n^{2015}$ it will take a while before the true colors show. – Jyrki Lahtonen Jan 30 '15 at 09:26
  • Ryan, $$\frac{f(n)}{g(n)}=\frac{3^n}{n\cdot2^n}=\frac{(3/2)^n}n.$$ Does that help? Usually courses on limits of sequences prove a general result dealing with ratios like this. – Jyrki Lahtonen Jan 30 '15 at 09:27

2 Answers2

2

Hint: For intuition, try taking the limit of the ratio

$$\lim_{n\rightarrow\infty}\frac{n2^n}{3^n}=\lim_{n\rightarrow\infty}n\left(\frac{2}{3}\right)^{n}$$

sbares
  • 4,063
0

Here is a proof without limits, just an induction. We prove that for all positive integers $n$, we have $g(n)\leq 3f(n)$: for $n=1$, we have $g(1)=2$ and $f(1)=3$, so it's fine.

Now, we have

$$\begin{align*} g(n+1) &= (n+1)2^{n+1} = \color{red}{n2^n}\cdot 2 + 2^n\cdot 2 \\ &\leq \color{red}{3\cdot3^n}\cdot2 + \color{blue}{2^n}\cdot2\\ &\leq 3^{n+1}\cdot2 + \color{blue}{\frac{3\cdot3^n}{n}}2 \\ &= 3^{n+1}\cdot(2+\frac{2}{n})\\ &\leq 3^{n+1}\cdot 3 = 3f(n+1).\end{align*}$$

Therefore, we have $g=O(f)$.

zarathustra
  • 4,891