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.
$\begingroup$
$\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
Add a comment
|
$\begingroup$
$\endgroup$
2
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$.
answered Sep 30 '16 at 2:14
-
$\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
$\begingroup$
$\endgroup$
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}$.
answered Sep 29 '16 at 22:34
$\begingroup$
$\endgroup$
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.
