0

I was wondering if my proof for this problem was correct.

Let $x = 2^n$. Then the problem reduces to is $x^2 = O(x)$, which is clearly false.

Dak Song
  • 151
  • 1
    Yes, provided that one notes the first $O$ is meant when $n\to\infty$, the second $O$ when $x\to\infty$ and that indeed if $x=2^n$ and $n\to\infty$ then $x\to\infty$. – Did Aug 02 '16 at 09:29
  • 1
    $2^{2n} = O(4^n)$ like $3^{n} = O(3^n)$ – Zau Aug 02 '16 at 09:31

1 Answers1

0

Note that $g(n) = O(2^n)$ if $\lim_{n \to \infty} \frac{g}{2^n} = c $ for some constant c. If you take the limit of the function you have you get infinity, which implies that your function $h(n) = \omega (2^n)$, which is a stronger condition.

Alex
  • 19,262