[Solved]: When does $1.00001^n$ exceed $n^{100001}$?

Problem Detail: 

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?

Asked By : David Faux

Answered By : Paresh

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/6711