Comparing order of growth with n^(logn) - need to know where value comes from?

Question

I'm trying to understand how you compare the following for order of growth.

With the below working out with $f_4$ I don't get where the $x^5$ and $x^6$ come from at the end. With $f_4$ you have $n^{\log n}$ when for example $\log 64$ doesn't equal 6? Can someone please explain where $x^5$ and $x^6$ come from?

Working out:

• $n = 32$, $f_1 = 2^{32}$, $f_4 = 32^5 = 2^{25}$
• $n = 64$, $f_1 = 2^{64}$, $f_4 = 64^6 = 2^{36}$

Compare these below

• $f_1(n) = 2^n$
• $f_2(n) = n^{3/2}$
• $f_3(n) = n \log n$
• $f_4(n) = n^{\log n}$

Answer 1

When you want to evaluate $f_4 = n^{\log_2 n}$ for some number, let's say 256, you first evaluate the exponent, $\log_2 n = \log_2 256 = 8$, then you put it into the full formula as $n^8 = 256^8$. Of course, since $256^8 = \left( 2^{ 8 } \right)^8 = 2 ^ {8 \cdot 8 } = 2^ {64}$.

Let's now do the exercises you have: for $n=32$, we have that $\log_2 n = \log_2 32 = 5$, hence $n^{5} = 32 ^ 5 = \left(2^{5}\right)^5 = 2^{5 \cdot 5} = 2^{25}$.

For $n = 64$, we have that $\log_2 n = \log_2 64 = 6$, thus $n^{6} = 64 ^ 6 = \left(2^{6}\right)^6 = 2^{6 \cdot 6} = 2^{36}$.

It seems to me that $n^{\log_2 n}$ follows the pattern of $2^{x^2}$ where $x = \log_2 n$.