1

Doing algorithm complexity analysis in my assignments, but don't know how to compare these two algorithm complexity,

$O(2^n)$ and $O((\log{n})^{\log{n}})$

Which one is larger and why?

Charlie Lam
  • 13
  • 4
    Is it $(\log n^{\log n})$ or $\log (n)^{\log n}$? –  Mar 07 '18 at 03:35
  • 1
    @idk If the former, we could just write $\log^2 n$ instead, so maybe the latter. – Mr Pie Mar 07 '18 at 03:40
  • 1
    @user477343 Then you can write it as $(\log n)\cdot (\log n)$ –  Mar 07 '18 at 03:42
  • Well, clearly $\lim_{n\to \infty}2^n$ approaches $\infty$ "faster". –  Mar 07 '18 at 03:43
  • 1
    @user477343 Or, better yet, $\log(n)^2$, which cannot be accidentally confused with $\log(\log(n))$. In any event, I'm not sure how to answer this question without clarification. I am also confused about the title---both limit are infinite, so neither is larger. Is the question about $\mathcal{O}(2^n)$ vs $\mathcal{O}((\log(n)^{\log(n)})$? – Xander Henderson Mar 07 '18 at 03:52
  • Sorry guys, my bad. Updated the second term. – Charlie Lam Mar 07 '18 at 05:08
  • @idk (and the upvoters of your comment) $(\log n^{\log n})$ and $\log (n)^{\log n}$ is the same. It is $\log n^{\log n}.$ I think you wanted to ask if it is $\log (n^{\log n})$ or $(\log n)^{\log n}$ – miracle173 Mar 07 '18 at 06:25
  • 1
    @user477343 $\log^2 n$ is usually (at least sometimes) used for $\log(\log n)).$ So it is more clear to write $(\log n)^2$ – miracle173 Mar 07 '18 at 06:37
  • @miracle173 for problems like that, I have my own notation.

    If we have $$\underbrace{\log_a^{ \ \ k}(\log_a^{
    \ k}(\log_a^{ \ \ k}\ldots\log_a^{ \ \ k}}{b\text{ times}} ,n)\ldots),$$then this is the same as writing $\log{(a, b)}^kn$.

     – Mr Pie Mar 07 '18 at 08:18
  • @XanderHenderson for problems like that, I have my own notation.

    If we have $$\underbrace{\log_a^{ \ \ k}(\log_a^{
    \ k}(\log_a^{ \ \ k}\ldots\log_a^{ \ \ k}}{b\text{ times}} ,n)\ldots),$$then this is the same as writing $\log{(a, b)}^kn$.

     – Mr Pie Mar 07 '18 at 08:18
  • 1
    @user477343 Okay... so you have your own idiosyncratic notation. I've never seen anyone else use that notation. Rather than introduce a new notation that might be confusing (again, is the $k$ representing the $k$-th power of $\log(n)$? Or is it the $k$-fold composition of the $\log$?), you are better off using standard notation, and doing so in a way that clearly indicates what you are doing when there is ambiguity (e.g. use more parentheses, explain the notation in the text). – Xander Henderson Mar 07 '18 at 14:37
  • @idk comment to my comment: $(\log n^{\log n})=\log n^{\log n}$, there is not otherway to interpret the parantheses. It is still unclear, what this means. If in $\log (n)^{\log n}$ the parantheses re used in the same way as in the previous expression (an unnecessary construct that enclosses $n$) then it can be removed and we end with $\log (n)^{\log n}=\log n^{\log n}$. But now I sess that it could be interpreted as part of the function symbol, and then $\log (n)^{\log n}= (\log (n))^{\log n}$ and the meaning of the expression is clear.I think the latter interpretation is the usual one. – miracle173 Mar 07 '18 at 18:32

1 Answers1

0

Intuitively, exponents matter much more than bases, so $2^n \gt \log n^{\log n}$
To be more careful $2^n=e^{n \log 2}, \log n^{\log n}=e^{\log n \log \log n}$ so you just need $n \log 2 \gt \log n \log \log n$

Ross Millikan
  • 374,822