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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
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 Rincón Fadul Feb 24 '12 at 19:46
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|cite|improve this answer

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

share|cite|improve this answer

Your Answer


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.