(logn)^(logn) = n^(log10+logn). WHY? [closed]

$\begingroup$

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}$.

$\endgroup$ 1

3 Answers

$\begingroup$

$$\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.

$\endgroup$ 1 $\begingroup$

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} $$

$\endgroup$ $\begingroup$

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. $$

$\endgroup$