When does $1.00001^n$ exceed $n^{100001}$?

Question

I have been told than $n^{1000001} = O(1.000001^n)$. If that's the case, there must be some value $n$ at which $1.000001^n$ exceeds $n^{1000001}$.

However, when I consult Wolfram Alpha, I get a negative value for when that occurs. http://www.wolframalpha.com/input/?i=1.000001%5Ex+%3D+x%5E1000001

Why is that? Shouldn't this value be really big instead of negative?

Answer 1

$f(n)$ = $O(g(n))$ implies that for all $n > N_0$, $N_0 > 0$, the relation $f(n) \leq c \cdot g(n)$ holds for some $c > 0$. Following this definition, we have:

$n^{1000001} \leq c \cdot (1.000001)^n$

$1000001 \cdot \log(n) \leq \log(c) + n \log(1.000001)$

Checking for $1000001 \cdot \log(n) = n \log(1.000001)$ on Wolfram, we find $N_0 = 3.10672*10^{13}$. For any $n \geq N_0$, if we select $c$ such that $\log(c) \geq 0$, the above relation will hold. Thus, $c \geq 1$ will suffice. Therefore, $n^{1000001} = O(1.000001^n)$.

More intuitively, $n^{1000001}$ is polynomial in $n$, whereas $1.000001^n$ is exponential in $n$. Since the exponent of the first term (1000001) is very large, and the base of the second term (1.000001) is nearly 1, it takes a long time for the exponential (in $n$) function to overtake the polynomial (in $n$) function, but it will overtake it eventually as it is a faster growing function asymptotically than a polynomial function. Informally, any polynomial function (polynomial in $n$) will be $O(g(n))$ where $g(n)$ is an exponential function in $n$.

Answer 2

The $n$ where the two expressions are equal isn't all that huge. Here's how to calculate it.

We want $$ 1.000001^n \approx n^{1000001}.$$ This is the same as
$$e^{n \log 1.000001} \approx e^{1000001 \log n}.$$ Now, taking the $\log$ of both sides, and using Taylor's formula to approximate the left-hand side, we get $$ n*10^{-6} \approx 10^6 \log n,$$ or $$\frac{n}{\log n} \approx 10^{12}.$$ Since this means $\log n \approx \log 10^{12},$ we get $$n \approx 10^{12} \log 10^{12} = 2.7 * 10^{13}. $$ More exactly, using Maple to solve the equation numerically (you have to give it the estimate above as a starting value or it gives up), we find that $n \approx 3.1*10^{13}$.

Answer 3

What you have been told is true. However the number where both function meet is huge (see Paresh' answer). There is also a second intersection point that you got with Wolfram. You can play around with smaller numbers of this pattern to get a feeling how large this value gets.

To see that the statement is true, it is the easiest to evaluate $$\lim_{n\to \infty} \frac{n^{10001}}{1.00001^n}.$$ Since can be done best with the rule of l'Hôspital. After taking 100001 derivatives of both enumerator and denominator you get $$\lim_{n\to \infty} \frac{n^{10001}}{1.00001^n}=\lim_{n\to \infty} \frac{0}{\ln 1.0001 \cdot 1.00001^n}=0.$$

Hence, $n^{10001}= O(1.0001^n)$.