# Multiplying exponents, solving for n

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.

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

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

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!

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.

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.

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.