-1
$\begingroup$

Based on the order by asymptotic growth rate which is more efficient?

$\endgroup$
3
  • $\begingroup$ It could depend on what base log you are using. Could you be more specific in the question? $\endgroup$ – Richie Yeung Jul 20 '20 at 14:05
  • $\begingroup$ it is base log 2 $\endgroup$ – Veree Jul 20 '20 at 14:08
  • $\begingroup$ If it is base 2 then the second term might as well be n. $\endgroup$ – Richie Yeung Jul 20 '20 at 14:12
1
$\begingroup$

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)}}&=\lim_{n\to\infty}\frac{\log(n+1+10^{n+1})-\log(n+10^n)}{1}\\ &=\lim_{n\to\infty}\log\left(\frac{(n+1)+10^{n+1}}{n+10^n}\right)\\ &=\lim_{n\to\infty}\log\left(\frac{(n+1)/10^n+10}{n/10^n+1}\right)\\ &=\log(10)\\ &>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)}$.

$\endgroup$
1
$\begingroup$

Roughly speaking:

$\begin{align*} \log_2 (2^n) &= n \\ \log_2(10^n + n) &> \log_2(10^n) \\ &= n \log_2 10 \end{align*}$

As $\log_2 10 = 3.3219$, the later is larger.

For rough comparisons, you can discard "lower terms" with impunity. In any case, often "asymptotic growth rate" applies only for very large $n$, and is usually meant to hide constant factors (check e.g. Hildebrand's "Short Course on Asymptotics" for details on the notation and manipulation techniques). If so, both are $\Theta(n)$, and more details are needed to compare fairly.

$\endgroup$
1
  • $\begingroup$ The last but one equality statement is false $\endgroup$ – droptop Jul 20 '20 at 17:24

Not the answer you're looking for? Browse other questions tagged or ask your own question.