1
$\begingroup$

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}$
$\endgroup$
3
  • $\begingroup$ (Think dualis instead of naturalis.) $\endgroup$
    – greybeard
    Dec 20, 2021 at 10:45
  • 1
    $\begingroup$ @greybeard how do you compare order of growth with (2^20) * n i.e how would you work that out? $\endgroup$
    – user146429
    Dec 20, 2021 at 11:19
  • $\begingroup$ Well actually, $\log_2 64$ does equal $6$. $\endgroup$
    – Nathaniel
    Dec 20, 2021 at 12:39

1 Answer 1

1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.