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