Which is more efficient? lg(n+10^n) higher than 2^lgn
Compute $\lim_{n\to\infty}\frac{\log(n+10^n)}{2^{\log(n)}}$. This is
$$\begin{align}\lim_{n\to\infty}\frac{\log(n+10^n)}{2^{\log(n)}}&amp;=\lim_{n\to\infty}\frac{\log(n+1+10^{n+1})-\log(n+10^n)}{1}\\
&amp;=\lim_{n\to\infty}\log\left(\frac{(n+1)+10^{n+1}}{n+10^n}\right)\\
&amp;=\lim_{n\to\infty}\log\left(\frac{(n+1)/10^n+10}{n/10^n+1}\right)\\
&amp;=\log(10)\\
&amp;&gt;1
\end{align}$$
where the first equation was using Stolz-Cesaro theorem (L'Hospital for sequences).
That this limit is larger than $1$ implies that for $n$ large enough $\log(n+10^n)$ becomes larger than $2^{\log(n)}$.