# Big O on $(1.0001)^n$ $n^{1.0001}$ and $2^\sqrt{logn}$ vs $1.0001^n$

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.

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

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