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.

$\endgroup$
5
  • $\begingroup$ $\sqrt{(100n^2)} \neq 10n^{2}$. But what you've done with the exponent at the end is right. $\endgroup$ Aug 13, 2012 at 17:58
  • $\begingroup$ ahh good catch thanks. $\endgroup$ Aug 13, 2012 at 17:59
  • $\begingroup$ 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. $\endgroup$ Aug 13, 2012 at 18:02
  • $\begingroup$ 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? $\endgroup$ Aug 13, 2012 at 18:05
  • $\begingroup$ There's no easy route that I am aware of. Just compute the numbers. $\endgroup$
    – copper.hat
    Aug 13, 2012 at 18:06

5 Answers 5

4
$\begingroup$

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

$\endgroup$
2
$\begingroup$

One of the answers says that problem can be stated as an inequality:

$$100n^2<2^n$$

Take $\log_{2}$ of both sides:

$$\log_2{(100n^2)} < n$$

By logarithm rules:

$$\log_2{(100)} + \log_2{(n^2)} < n$$

You may remove the squared term (I'm not sure if this matters):

$$\log_2{(100)} + 2\log_2{(n)} < n$$

Rearrange by subtracting $ 2\log_2{(n)}$ from both sides:

$$\log_2{(100)} < n- 2\log_2{(n)}$$

Square both sides:

$$(\log_2{(100)})^2 < (n- 2\log_2{(n)})^2$$

Expanding out the brackets, this may be expressed as a quadratic:

$$ n^2 - 4\log_2{(n)}n + 4(\log_2{(n)})^2 - (\log_2{(100)})^2 > 0$$

Now we must solve for $n$.

Wolfram Alpha

one of the solutions is $ n > 14.3247$ which is what one of the other answers shows in the linear plot.

This might be a very convoluted way to go about it, _'m not sure. But the other answer involved plotting and looking to narrow down. That might be found with newton iteration algorithm as well. But this quadratic way I think is a direct way to get the answer. The other root is less than 1 so I guess it can be ignored.

I'm very happy to be shown if there's a simpler way!

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

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