How to determine $10^{\log n}$ and $3n^2$ which grows faster asymptotically?

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.

– D.W.
Commented Sep 29, 2016 at 22:35
• What does "ranks before" mean? Commented Sep 29, 2016 at 23:06
• 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. Commented Sep 30, 2016 at 7:34
• 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. Commented Sep 30, 2016 at 8:58
• I would always recommend using lb or log2, ln, or log10 and never a naked log. Commented Sep 30, 2016 at 13:34

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

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

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

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.