1
$\begingroup$

I want to show, that $2^n \in \Omega(n^{\log_2 \log_2 n})$, thus I want to show, that there is a value $n_0$ from which on $2^n$ will always be bigger than $n^{\log_2 \log_2 n}$.

$2^n \geq n^{\log_2 \log_2 n}$

I have thought about induction and limiting values, however it didn't seem to work. I have also thought about showing that $2^n$ is growing faster through:

$\lim_{n \rightarrow \infty} \frac{2^n}{n^{\log_2 \log_2 n}}$

And using L'Hospital or is there an approach which is more obvious?

  • 0
    The last inequality $2^{\log\log{n}} \geq n^{\log\log{n}}$ is certainly wrong (take $n = 3$, for exmple). So you already have reduced to $n \geq (\log_2{n})^2$. By taking $\log$'s on both sides of that last inequality you get $\log{n} \geq 2 \log{\log{n}}$. It should be easy to see when that holds.2011-10-27

1 Answers 1

4

Big hint: the logarithm function is strictly increasing on $\mathbb{R}^{+}$; that is, if $x\lt y$, $\log_2(x)\lt\log_2(y)$. Applying this to both sides of the inequality you're trying to prove will give a much easier inequality. The key tool is the fact that $(\log n)^t\in o(n)$ for all values of $t$ (and so $\log\log n\in o(\log n))$; you'll want to apply this twice.