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
