# Pretty simple question about running time

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?

-
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

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).
I find that the first integer such that $100n^2 < 2^n$ is $n=15$. Is this what you wanted?