(logn)^(logn) = n^(log10+logn). WHY?

5,484

Solution 1

$$\log(n)^{\log(n)} = \left ( b^{\log(\log(n))} \right )^{\log(n)}=(b^{\log(n)})^{\log(\log(n))}=n^{\log(\log(n))}$$

assuming the log is base $b$. Since $\log(\log(n))$ is growing, this grows faster than just $n$ which has a fixed exponent.

Solution 2

Taking the logarithm of both $\log n^{\log n}$ and $n^{\log \log n}$, we have $$ \log\left(\log n ^{\log n}\right) = \log n \cdot \log\log n $$ and $$ \log\left( n^{\log\log n}\right) = \log\log n \cdot \log n $$ Therefore, $$ \log n ^{\log n} = n^{\log \log n} $$

Solution 3

We need to check the equality: $$ (\log n)^{\log n} = n^{\log \log n} \tag{1} $$

Let $n=e^a>1$, then $\log n = a$, and it is easy to see that both sides of $(1)$ are equal to $a^a$: $$ (\log n)^{\log n}=a^a \quad\mbox{ and } \quad n^{\log \log n} =e^{a\log a}=a^a. $$

Share:
5,484

Related videos on Youtube

merry-go-round-one
Author by

merry-go-round-one

SWE at Google

Updated on November 10, 2020

Comments

  • merry-go-round-one
    merry-go-round-one almost 3 years

    I'm comparing $f(n)$: O(logn^logn) vs. $g(n)$: O(n/logn).

    I multiplied logn to both sides, then it will be logn^(1+logn) vs n.

    Question: what do we do here next to compare two functions?


    My solution for textbook says,

    $f(n)$ is $n^{\log\log n}$ , so $f(n)$ is superior to $g(n)$. $\leftarrow$ I don't understand why it's $n^{\log\log n}$.

    $\leftarrow$ I guess $n^{\log\log n}$ is $n^{\log 10+\log n}$.

    • gen-ℤ ready to perish
      gen-ℤ ready to perish almost 6 years
      Please use MathJax to format your posts.
  • merry-go-round-one
    merry-go-round-one almost 6 years
    I don't understand why logn is equivalent to b^log(logn(n)). Can you illustrate it on answer?