Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 0 down vote favorite

What is the smallest value of $n$ such that an algorithm whose running time is $100n^2$ runs faster than an algorithm whose running time is $2^n$ on the same machine?

share|improve this question
1  
For an exact answer, solve $100n^2=2^n$ using Labert's W-function. For an approximate solution, note that $100(14)^2=19600\gt 16384=2^{14}$, but $100(15)^2 = 22500\lt 32768=2^{15}$, so they cross over somewhere between $n=14$ and $n=15$. – Arturo Magidin Feb 24 '12 at 19:41
Just doing some arithmetic, it's $n=15$. – David Mitra Feb 24 '12 at 19:42
Thanks @ArturoMagidin didn't know about Lambert's W function. Actually that's the solution. – Randolf R-F Feb 24 '12 at 19:46

2 Answers

up vote 2 down vote accepted

On the one hand, you could just plug in some numbers and see what pops up. Here, you know you only care about 4 digit values of $2^n$, so perhaps start at $2^{12}$ or something. It turns out that $n=15$ is the smallest integer.

However, we should also know that runtimes are usually expressed up to a constant of multiplication. So perhaps it's actually $16$ or $14$ (though both are unlikely here, because of the large differences).

share|improve this answer
up vote 0 down vote

I find that the first integer such that $100n^2 < 2^n$ is $n=15$. Is this what you wanted?

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.