5
$\begingroup$

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.

  • 0
    There's no easy route that I am aware of. Just compute the numbers.2012-08-13

5 Answers 5

4

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

Since the rate of increase of $n\mapsto 10n$ is constant, while $n\mapsto 2^{n/2}$ grows more and more quickly for larger $n,$ it follows that $10n<2^{n/2}$ whenever $n\ge 20,$ so we're looking for some $n<20.$


Trying $n=14$ gives us $10n=140$ and $$2^{n/2}=128,$$ so by similar reasoning, we need some $n\ge 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$.

1

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.

0

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.

0

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.