0

More specifically, I am trying to show that the asymptotic complexity of a problem with that has the bounds $\Theta(\log{2}(n) ^{(\log_2(\log_2(n))})$ is less than that of a problem with the bounds $\Theta(n)$.

I tried to use L'Hospital's rule but the derivatives become too complicated for that to be a good solution. I suspect that there may be a substitution that I can make, but if there is I cannot see what it is.

Edit: I originally stated that the log term was greater, which is clearly an error.

enter image description here

greedIsGoodAha
  • 145
  • 6
    take $\log_2(\cdot)$ from both sides. – dezdichado Sep 01 '17 at 21:27
  • 2
    Sure that this inequality holds for large $n$ ? numerical calculations indicate the opposite inequality. For example, for $\large n=10^{10^5}$, I get $1.87\cdot 10^{101}$, which is much smaller – Peter Sep 01 '17 at 21:30
  • @Peter: I was wrong before; I misinterpreted the question. Sorry :( – Clayton Sep 02 '17 at 04:14

2 Answers2

6

I think you mean the inequality should be the other way around ? Take $ \log_2 $ of the inequality \begin{eqnarray*} \log_2 (n) \leq \left( \log_2( \log_2 (n)) \right)^2 \end{eqnarray*} Now let $n=2^{2^N}$ and we get \begin{eqnarray*} 2^N \leq N^2 \end{eqnarray*} which is obviously false for large $N$

Peter
  • 84,454
Donald Splutterwit
  • 36,613
  • 2
  • 26
  • 73
1

The inequality goes the wrong way. $$(\log_2 n)^{\log_2 \log_2 n} = 2^{(\log_2 \log_2 n)^2}$$ while $$n = 2^{\log_2 n}$$ Now $\log_2 t = o(t^\alpha)$ for any $\alpha>0$ as $t \to \infty$. Taking $t = \log_2 n$ we have $\log_2 \log_2 n = o((\log_2 n)^{1/2})$ and $(\log_2 \log_2 n)^2 = o(\log_2 n)$.

Robert Israel
  • 448,999