Disprove $f(n) = 2^{2n}$ is $O(2^n)$

Question

Informally I know that this means we have to show that $2^{2n}$ grows much faster than $2^n$.

More formally, I know that we need to show that for any $N$, there is a constant $c>0$, so that for all $n>N$ such that $2^{2n}>c\cdot 2^n$.

I am not sure how to derive $N$ and a fixed constant $c$ in order to disprove this proposition. Can anybody show me how?

score 2 · Accepted Answer · answered Jun 05 '15 at 03:33

2

Hint: $$\frac{2^{2n}}{2^n}=2^n$$

answered Jun 05 '15 at 03:33

Teoc

I feel like I am close to understanding, but not quite there. Can you explain how that helps me solve the problem? – User Jun 05 '15 at 03:36
@OmarN From your last inequality, $2^{2n}>c2^n$, we find that $2^n>c$, which is true because $2^n$ takes on all values from $0$ to $\infty$, which is clearly greater than C. – Teoc Jun 05 '15 at 03:43

1 Answers1