Take the 2-minute tour ×
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.

"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|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
add comment

1 Answer 1

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|improve this answer
add comment

Your Answer

 
discard

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.