0
$\begingroup$

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?

  • 0
    Thanks @ArturoMagidin didn't know about Lambert's W function. Actually that's the solution.2012-02-24

2 Answers 2

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?