(logn)^(logn) = n^(log10+logn). WHY?
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. $$
Related videos on Youtube
Comments
-
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 belogn^(1+logn)
vsn
.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 almost 6 yearsPlease use MathJax to format your posts.
-
-
merry-go-round-one almost 6 yearsI don't understand why logn is equivalent to b^log(logn(n)). Can you illustrate it on answer?