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
-
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?