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.

When solving for n in this equation I get stuck.

Question: What is the smallest value of n such that an algorithm with running time of $\ 100n^2 $ runs faster than an algorithm whose running time is $\ 2^n $ on the same machine?

Straight out of CLRS chapter 1. Class starts in 2 months wanted to get a head start.

My approach:

$\ 100n^2 = 2^n $

$\ \sqrt(100n^2) = \sqrt(2^n) $

$\ 10n = (2^n)^{1/2} $

$\ 10n = (2^{n/2}) $

Is this last step correct? I know I add exponents when multiplying but this is raising an exponent to an exponent so I should multiply. I'm still unsure how to bring the n down out of the exponent on the two so I can solve for it.

share|improve this question
    
$\sqrt{(100n^2)} \neq 10n^{2}$. But what you've done with the exponent at the end is right. –  SiliconCelery Aug 13 '12 at 17:58
    
ahh good catch thanks. –  The Internet Aug 13 '12 at 17:59
    
The fact that $10n=2^{n/2}$ may help a little. But there is no way to solve the resulting equation by "formula." (I am lying slightly.) You will need to fool around a bit with numbers to get an answer. –  André Nicolas Aug 13 '12 at 18:02
    
I can't divide by 2 either since the expression on the right contains a variable in the exponent. Any hints on how I can express $\ 2^n $ in a way that makes it more conducive to be solved by 10n? –  The Internet Aug 13 '12 at 18:05
    
There's no easy route that I am aware of. Just compute the numbers. –  copper.hat Aug 13 '12 at 18:06

4 Answers 4

up vote 3 down vote accepted

Sometimes in cases like this, it's useful to simply try a few and see what happens. Trying $n=20$ gives $10n=200$ and $2^{n/2}=2^{10}=1024$, so $n\leq 20$. Trying $n=14$ gives us $10n=140$ and $2^{n/2}=128$, so $n>14$. From there, the solution's fairly quickly found to be $n=15$.

Note: $n=15$ is not the solution to the equation $100n^2=2^n$, but it is the least $n$ for which $100n^2<2^n$.

share|improve this answer

This is correct. You can then start guessing to find it by hand. Clearly for $n=20$ left hand side is much smaller than right hand side. For $n=16$ similarly, $n=15$ seems okay, since $2^7=128$ and $\sqrt 2>1.4$, and $n=14$ is too small for similar reasons.

share|improve this answer

The equation $10 n = 2^{n/2}$ can't be solved in terms of elementary functions: you have to use the Lambert W function. The two real solutions are $-2 LambertW(-\ln(2)/20)/\ln(2)$ and $-2 LambertW(-1,-\ln(2)/20)/\ln(2)$. But for what you want to do, this is not very relevant. "Guess and check" is the way to go.

share|improve this answer

I used Wolfram to narrow down on the approximate solution. I started with:

plot 2^x - 100 *x^2 , x=1 to 100

and looked at the graph to narrow the value of n down to:

plot 2^x - 100 *x^2 , x=14.3245 to 14.325

http://www.wolframalpha.com/input/?i=plot+2^x+-+100+*x^2+%2C+x%3D14.3245+to+14.325

after a couple steps.

This was after trying to reduce it to the simplest terms though my knowledge doesn't make it to Lambert functions.

share|improve this answer

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.