Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question
1  
The answer you got from WA is actually a complex number ($\approx -1 - 10^{-6}\pi i$); their typography makes this less than obvious. –  Zack Nov 17 '12 at 15:52
1  
If you rearrange the expression a little, you can find that the answer is around $3 \times 10^{13}$. –  mhum Nov 18 '12 at 20:22

3 Answers 3

up vote 6 down vote accepted

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

share|improve this answer

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

share|improve this answer
    
Sure, if you're counting atoms. :-) –  John Moeller Nov 28 '12 at 3:14
2  
Actually, $3.1*10^{13}$ is tiny when compared to the running time of the polynomial algorithm at $n=2$. :-) –  Peter Shor Nov 28 '12 at 3:46

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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