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
    t.b. How is $2^n \geq 2^{\log_2 n \cdot \log_2 \log_2 n}$ is what I want?2011-10-27
  • 0
    Sorry, I accidentally removed my comment. I suggested to try and prove $n \geq \log_2{n}\cdot\log_{2}\log_2{n}$.2011-10-27
  • 0
    t.b.: No problem, but I am not completely understanding why this is sufficient.2011-10-27
  • 0
    if $x \geq y$ then $2^x \geq 2^y$ take $x = n$ and $y = \log_2{n} \cdot \log_2\log_{2}n$ and observe that $2^{y} = n^{\log_2\log_2n}$.2011-10-27
  • 0
    in order to prove inequality that t.b suggested use substitution $\log_{2} n=t$2011-10-27
  • 0
    t.b. This is neat, now I understand it. But I am still having troubles to show that $n \geq log_2 n \cdot log_2 log_2 n$. I tried already by removing one $\log_2 n$ because this should not break the inequality: $n \geq log_2 n \cdot log_2 n$. But it didn't really help me.2011-10-27
  • 0
    Anoter solution: Isn't it just enough to show it with the following more obvious inequality: $2^n \geq 2^{(log n)} \geq 2^{(log log n)} \geq n^{(log log n)}$2011-10-27
  • 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.