Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
have you tried with logarithms? – dineshdileep Jan 3 '13 at 12:10
It should be $n=15$ since $2^{14}-100\cdot 14^2=-3216.$ – coffeemath Jan 3 '13 at 12:25
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. – Siméon Jan 3 '13 at 12:41
up vote 0 down vote accepted

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$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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