3
$\begingroup$

is there any difference between $\log(n)^{\log(n)}$ vs $(\log n)^{\log n}$ vs $\log n^{\log n} $ from asymptotic growth rate? maybe all the same. I doubt about notation.

maybe this is very basic or crazy question, but I need to know.

$\endgroup$
1
  • 4
    $\begingroup$ The notation of $\log(n)^{\log n}$ and $\log n^{\log n}$ are both ambiguous. $\log(n)^{\log n}$ probably means $(\log n)^{\log n}$ but it could mean $\log[n^{\log n}]$. $\log n^{\log n}$ probably means $\log[n^{\log n}]$ but it could mean $(\log n)^{\log n}$. $\endgroup$
    – fleablood
    Nov 23 '20 at 6:19
4
$\begingroup$

One must be careful, there is a crucial difference between $$(\log n)^{\log n}$$ and $$\log n^{\log n}$$ The exponent rule for the logarithm can be applied to this last one to obtain: $$\log n^{\log n}= \log n \log n=(\log n)^2 \neq (\log n)^{\log n}$$

$\endgroup$
1
  • $\begingroup$ please add details for the first expression in question. $\endgroup$ Nov 23 '20 at 8:56
2
$\begingroup$

Yes there is. Simple thumb rule: Power on the operand comes to side.

Suppose there is a logarithm exprerssion $\log_a{x}, a\neq1, x\gt0$. I am going to refer $x$ as the operand.Now, if an exponent $y$ is present on the operand $x$, then:

$$\log_a{(x^{y})} = y\log_a{x}$$

Proof: Here I am considering $y\ge0$ (since I am assuming growth rates require only positive integral domain). A similar proof is present for negative y too. $$\log_a{(x^{y})} = \log_a{(x\times x \times x\times x...y\ times)} = \log_a{x}+\log_a{x}+\log_a{x}...y \ times = y\log_a{x}$$

The other one is simply

$$(\log_a{x})^y = \log_a{x}\times\log_a{x}\times\log_a{x}...y \ times$$

EDIT: $\log{(n)}^{\log{(n)}}$ is a little ambiguous. If up to me, I would consider it as an exponent on the operand (just because parenthesis are there about n)

EDIT 2: To put it simply, one growth is polynomial$\times$logarithmic and other logarithmic exponentiated to logarithmic. To find the actual difference, you could find the ratio of their limits as n$\to\infty$. Then you can compare their relative growth rates.

$\endgroup$
2
  • $\begingroup$ Your proof is valid only when $y$ is a positive integer. $\endgroup$ Nov 23 '20 at 6:24
  • $\begingroup$ @BrianCheung , I know, but the formula is valid nonetheless for negative $y$ too. And since OP is asking about asymptotic growth rates, n has to be positive. Still, I will edit it in the answer $\endgroup$
    – Aman Kumar
    Nov 23 '20 at 6:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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