# Solving for n: power and log rules refresh

1. Sep 28, 2016

### nrobidoux

1. The problem statement, all variables and given/known data

A computer can perform 1010 ops/s. Assume 1 op per 1 input. Given the following algorithmic complexities how many inputs can be performed in an hour.

• n2
• n3
• 100n2
• n log n
• 2n
• 22n
2. Relevant equations

3. The attempt at a solution

C = 1·1010 ops/s · 3.6·102 s/hr
C = 3.6·1012 ops/hr

Set each complexity equal to C.

I know this is almost basic algebra but I haven't done this in decades. I think I'm good in the first 3... it's the last 3 I'm a bit confused on. Mostly n log n. Did some googling of the rules but I'm still confused there, and I've never seen a log of a log...

----------------------------------------------
n2 = C
n
(2 · 1/2) = C 1/2
n = C 1/2

----------------------------------------------
The next is basically the same except it's cubic: n = C 1/3

----------------------------------------------
100n2 = C
n
2 = C/100
n(2 · 1/2) = (C/100)1/2
n = (C/100)1/2

----------------------------------------------
n logb( n ) = C

... (more Googling)...

I have no clue... I found another rule. On the surface I think I applied them correctly but I don't know how to get n by itself. I got: bC = nn and bC/n = n.... of course if I really looked at those two...

----------------------------------------------
2n = C
n
= log2 ( C )

----------------------------------------------
22n = C
2n = log2 ( C )
n = log2 ( log2 ( C ))

2. Sep 29, 2016

### haruspex

Check that.
No base was given.
You only need a solution that is asymptotically correct. Given y log y = x, make a guess as to what y is, approximately, as a function of x.

3. Sep 29, 2016

### Ray Vickson

The solution to $n \log_2(n) = C$ involves the so-called Lambert W-function, which is non-elementary (not a simple power, root, trig, exponential, etc.) Maple gets the solution
$$n = \frac{C \ln(2)}{W(C \ln(2))},$$
where $W(w)$ is the Lambert-W function of $w$.

4. Sep 29, 2016

### nrobidoux

I used https://www.desmos.com/calculator to get an answer. I'll ask the professor for some clarification.

n = 1.13 ·1011
for n log10 ( n ) = C

The Lambert-W function as part of the solution sounds a bit too complicated for a day 1 homework problem. I think all these were intended to be solved with a pen and paper. Was the application of log rules applied correctly to the last problem? The 22n?

As for the 3.6·102 s/hr ... easy peasy with simple tricks. 60 sec/min x 60 min/hr.. units cancel to sec/hr 6X6 = 36. Add 2 zeroes. 3.6·102 Honestly thought it was 36·102 but Google docs is converting 3.6E2 to ... err well yesterday it was confusing me. So changing the power to 13 from 12 in C. I get 2.9 ·1012 above.

5. Sep 29, 2016

### haruspex

As I posted, you only need an approximation. Go on, make a guess as to how y depends on x, roughly, if y log y = x.

6. Sep 29, 2016

### Ray Vickson

Obviously we are talking about two different problems! I gave you a formula for solution that involved the symbolic C, just as you had done for problems A-C and E-F. I was pointing out to you that a symbolic answer involves a new function that you probably have never heard of before (but which is, in fact, used a lot in combinatorics and computer science). Of course if somebody gives you a numerical value of C you have a completely different situation, where some good guesses and a few trial values will get you a usable solution quickly. But, you need a numerical value for C in order to do that.

If your computer is loaded with a spreadsheet such as EXCEL, you can solve such equations by calling on the "Solver" tool, so you don't need to go to some on-line package if you would rather not.

7. Sep 29, 2016

### nrobidoux

I'll see if my version has that. It's an old version of Excel. I can be a bit slow when it comes to math.... I have the answer but just want to be able to understand the process to get there in case it pops up on a test. It happens to be proctored online somehow. I asked for some clarification on the base.... see what happens. I got quite a few days before this is due.

C = 3600 * 10^10

I appreciate the help. Forum is awesome. :D

8. Sep 30, 2016

### haruspex

I'll add a hint. To a first approximation, x and y would be of similar magnitude. Use that to substitute for one of the occurrences of y.