0
$\begingroup$

i have a problem with proof one of this facts:

$2^{2^n}$ = $\Theta (n^n)$ or

$2^{2^n}$ = $O (n^n)$ or

$2^{2^n}$ = $\Omega (n^n)$

and to proof one of this:

$(n^n)$ = $\Theta (2^{2^n})$

$(n^n)$ = $O (2^{2^n})$

$(n^n)$ = $\Omega (2^{2^n})$

There is asymptotic notation above. I would be appreciate even for some tips to count this. How to proof that? Thanks

  • 0
    Then you know that $O$ is somewhat simpler than $\Theta$, don't you? So let us start with the second proposition: assume that $2^{2^n}=O(n^n)$. First: what does the assertion mean? Next: does it hold?2012-04-09

1 Answers 1

2

Some hints to get you started:

The entire problem is about comparing the rates of growth of $n^n$ and $2^{2^n}$: do they grow at roughly the same rate, does $n^n$ grow a lot faster than $2^{2^n}$, or does $n^n$ grow a lot slower than $2^{2^n}$?

One way to investigate this is to consider the limit of their ratio as $n$ increases, $\lim_{n\to\infty}\frac{n^n}{2^{2^n}}\;.\tag{1}$ This is a bit messy to think about in this form, but you could write it in a more manageable form by using the fact that $n=2^{\lg n}$, where $\lg n=\log_2 n$. Warning: There are three $n$’s in $(1)$, and only one of them should be subjected to this substitution.

Once you have $(1)$, you can use it to address the technicalities of showing which of $\Theta,O$, and $\Omega$ applies in each part of the problem.

  • 0
    I count this with L'Hôpital's rule :)2012-04-22