6
$\begingroup$

My think is pretty easy that $10^{\log n} = n$, which is growing slower than $3n^2$.

However, many tutorial shows that $3n^2$ ranks before $10^{\log n}$.

I'm really confused.

$\endgroup$
5
  • 2
    $\begingroup$ cs.stackexchange.com/q/824/755 $\endgroup$ – D.W. Sep 29 '16 at 22:35
  • 3
    $\begingroup$ What does "ranks before" mean? $\endgroup$ – David Richerby Sep 29 '16 at 23:06
  • 1
    $\begingroup$ Take extreme care when you see a "log" to make sure that everyone agrees on the base. In this case, the base is essential to the answer. $\endgroup$ – gnasher729 Sep 30 '16 at 7:34
  • 1
    $\begingroup$ In computer science, the base is almost always 2, unless the context involves serious mathematics in which case it may be $e$. Any other base would be mentioned explicitly with a big fat warning. $\endgroup$ – Emil Jeřábek Sep 30 '16 at 8:58
  • $\begingroup$ I would always recommend using lb or log2, ln, or log10 and never a naked log. $\endgroup$ – gnasher729 Sep 30 '16 at 13:34
8
$\begingroup$

You have to be careful here, since the answer depends on the particular log function you use. As Lieuwe noted if $\log$ in this context means $\log_{10}$ then $10^{\log n}=n$ and certainly $n$ "ranks before" $3n^2$, under any reasonable interpretation of "ranks before". However, if we have a different base for the logarithm, that might not be the case.

It's not hard to show that $10^{\log_b n}=n^{log_b{10}}$ (take the log of both sides) and so $10^{\log_b{n}}$ will be asymptotically larger than $n^2$ as long as $\log_b10>2$, i.e., when $b^2<10$, so when you use logs to base $b$ with, say, $b=3$ you'll have $10^{\log_b n}$ "ranks after" $3n^2$.

$\endgroup$
2
  • $\begingroup$ If b is smaller than sqrt(10) it is growing slower and if b is larger than sqrt(10), it is growing faster. $\endgroup$ – Uwe Sep 30 '16 at 8:03
  • $\begingroup$ Good point, I hadn't considered how the base of the logarithm might decide the question. $\endgroup$ – Lieuwe Vinkhuijzen Sep 30 '16 at 9:54
4
$\begingroup$

If you are using base 10 log, then yes, $10^{\log n}=n$. It has lower asymptotic growth than $3n^2$, as you note, because for every $c$, there is an $n_0$ such that $3n^2>cn$ for all $n$ which are greater than $n_0$. Proving this is an exercise for the reader.

If you read that $3n^2$ ranks before $10^{\log n}$, then those sources are wrong. There are other functions that look superficially similar that do grow faster, such as $n^{\log n} = 10^{(\log n)^2}$ and $\log n^{\log n}=10^{\log n \cdot \log\log n}$.

$\endgroup$
0
$\begingroup$

As others have noted, it depends on the base of the $log$. When a base is not given, in computer science it is generally assumed to be 2. In mathematics, it is generally assumed to be $e$. In engineering, it is generally assumed to be 10.

$\endgroup$

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.