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?
Pretty simple question about running time
0
$\begingroup$
algorithms
inequality
-
1For an exact answer, solve $100n^2=2^n$ using Labert's [W-function](http://en.wikipedia.org/wiki/Lambert%27s_W). 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$. – 2012-02-24
-
0Just doing some arithmetic, it's $n=15$. – 2012-02-24
-
0Thanks @ArturoMagidin didn't know about Lambert's W function. Actually that's the solution. – 2012-02-24
2 Answers
2
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).
0
I find that the first integer such that $100n^2 < 2^n$ is $n=15$. Is this what you wanted?