2
$\begingroup$

It's been a while since I touched limits/calculus so I'm a little iffy on the problem below. Given the two sequences

$(1.0001)^n$

$n^{1.0001}$

which one grows faster? My reasoning is that $(1.0001)^n$ or aka 1.0001 multiplied to itself n times will approach infinity but it grows at a slow rate, $n^{1.0001}$ is bigger in most cases and will definitely approach infinity but at a faster rate so $(1.0001)^n$ = O($n^{1.0001}$).

Then $2^\sqrt{\log n}$ vs $1.0001^n$ I thought that $2^\sqrt{\log n}$ > $1.0001^n$ since if we log both sides we get

$\sqrt{\log n}$ and $\log(1.0001^n)$ , again multiplying 1.0001 to itself n times grows really slowly while $\sqrt{\log n}$ has a square root but might grow at a faster rate, so $\log(1.0001^n)$ = O($\sqrt{\log n}$ ).

But my reasoning might be wrong.

$\endgroup$
  • 1
    $\begingroup$ $\log (1.0001^n) = n \log (1.0001)$; this grows linearly, which is clearly larger than $\log n$ or $\sqrt{\log n}$. $\endgroup$ – Batman Jan 10 '17 at 22:51
4
$\begingroup$

No. $(1.001)^n$ is larger than $n^a$ for any constant $a$, asymptotically. This is easy to see: $\lim_{n \to \infty} \log \frac{(1.001)^n}{n^a} = \lim_{n \to \infty} n \log (1.001) - a \log n = \lim_{n \to \infty} n ( \log 1.001 - a \frac{ \log n }{ n} ) = \infty$ since $\frac{ \log n}{n} \to 0$. Since log is monotone increasing, this implies $n^a = O(1.001^n)$.

Now, apply a similar argument for $2^{\sqrt{\log n}} = e^{\sqrt{\log n} \log 2}$ versus $(1.001)^n = e^{n \log 1.001}$ (it suffices to compare the exponents; there exists a $N$ such that $n \log 1.001 > \sqrt{\log n} \log 2$ for all $n \geq N$ so $2^{\sqrt{\log n}} = O((1.001)^n)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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