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

I know the answer is $n = 15$, but is there any way to solve this without trial and error?

$\endgroup$
3
  • $\begingroup$ have you tried with logarithms? $\endgroup$ – dineshdileep Jan 3 '13 at 12:10
  • $\begingroup$ It should be $n=15$ since $2^{14}-100\cdot 14^2=-3216.$ $\endgroup$ – coffeemath Jan 3 '13 at 12:25
  • $\begingroup$ You can start by plotting the function $x\mapsto 2^x - 100x^2$. After this, you just have to check that the value you found is correct. $\endgroup$ – Siméon Jan 3 '13 at 12:41
0
$\begingroup$

Trial and error is necessary, unless you use Lambert's W-function. In maple, the request for a solution to $2^x=100x^2$ gave two complicated expressions involving the Lambert function $W(x)$. Numeric evaluation of these gave the real values $0.103657...$ and $14.324727...$, making the answer $15$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.