0
$\begingroup$

The problem I have is asking me if $2^{2^{n + 1}} = O( 2^{2^n} )$?

This is my proof:

let constant $C = 16$, and $k = 1$ such that for all $n \geq k$
let $n = 1$

1: $2^{2^{1 + 1}} \leq C 2^{2^1}$
2: $2^{2^2} \leq 16 2^2$
3: $2^4 \leq 16 4$
4: $16 \leq 64$ is true. Q.E.D.

Did I properly prove that $2^{2^{n + 1}} == O( 2^{2^n} )$? Is there anything else I need to show for this proof to be complete?

  • 1
    No. You simply shows that $$2^{2^{1+1}}<16\times 2^{2^{1}}$$ which is not what big O notation refers to. Any single value of the functions is irrelevant for big O inequalities; all that matters is the asymptotic behavior, that is how the functions compare as $n$ goes to $\infty$. I suggest you look at [wikipedia](http://en.wikipedia.org/wiki/Big_O_notation).2012-01-16
  • 1
    You should inclose the LaTeX code in $\$\dots \$$. Please take a look at the edited file to learn how to do it.2012-01-16
  • 0
    $${2^{2^{n+1}}\over 2^{2^n}}=2^{2^{n+1}-2^n}=2^{2^n}$$2012-01-16
  • 0
    Sorry David but what is $ 2^{2^n} $ showing me?2012-01-16

1 Answers 1

2

Your proof is incorrect; you showed that $2^{2^{n+1}}\le C\cdot 2^{2^n}$ for one value of $n$. If you want to show that $2^{2^{n+1}}=O( 2^{2^n})$, then you need to find a positive constant $C$ so that $$\tag {1}2^{2^{n+1}}\le C \cdot2^{2^n}$$ for all $n$ sufficiently large (note the same $C$ must work for all $n$ sufficiently large).

But as $$\tag{2} 2^{2^{n+1}} =2^{2\cdot 2^n}=2^{2^n+2^n} = 2^{2^n}\cdot 2^{2^n}, $$ this would be impossible to do.

Indeed, suppose $C>0$ and that $(1)$ holds for all $n>m$.

Then from $(2)$ $$ 2^{2^n}\cdot 2^{2^n}\le C \cdot2^{2^n};$$ whence $$ 2^{2^n} \le C, $$ for all $n>m$. But this can't happen since $\lim\limits_{n\rightarrow\infty} 2^{2^n}=\infty$.

  • 0
    Are you saying C is = $ 2^{2^n} $ and because of n, C can't be a constant making $2^{2^{n+1}}\le C\cdot 2^{2^n} $ not true?2012-01-16
  • 0
    @TheFuzz More or less. $C$ must be positive constant. But because of the above, there isn't one. I'll expand the answer.2012-01-16