snippetMinor
How to determine $10^{\log n}$ and $3n^2$ which grows faster asymptotically?
Viewed 0 times
growslogasymptoticallyandfasterdeterminehowwhich
Problem
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.
However, many tutorial shows that $3n^2$ ranks before $10^{\log n}$.
I'm really confused.
Solution
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$.
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$.
Context
StackExchange Computer Science Q#64053, answer score: 8
Revisions (0)
No revisions yet.