Solving for n: power and log rules refresh

[nrobidoux]

Homework Statement

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

• n²
• n³
• 100n²
• n log n
• 2ⁿ
• 2²ⁿ

Homework Equations

The Attempt at a Solution

[/B]
C = 1·10¹⁰ ops/s · 3.6·10² s/hr
C = 3.6·10¹² 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...

----------------------------------------------
n² = 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

----------------------------------------------
100n² = C
n² = C/100
n^{(2 · 1/2)} = (C/100)^1/2
n = (C/100)^1/2

----------------------------------------------
n log_b( 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: b^C = nⁿ and b^C/n = n... of course if I really looked at those two...

----------------------------------------------
2ⁿ = C
n = log₂ ( C )

----------------------------------------------
2²ⁿ = C
2ⁿ = log₂ ( C )
n = log₂ ( log₂ ( C ))

 

[haruspex]

3.6·102 s/hr

Check that.

n log_b( n ) = C

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.

 

[Ray Vickson]

Homework Statement

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

• n²
• n³
• 100n²
• n log n
• 2ⁿ
• 2²ⁿ

Homework Equations

The Attempt at a Solution

[/B]
C = 1·10¹⁰ ops/s · 3.6·10² s/hr
C = 3.6·10¹² ops/hr

Set each complexity equal to C.----------------------------------------------
n log_b( 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: b^C = nⁿ and b^C/n = n... of course if I really looked at those two...

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

 

[nrobidoux]

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

n = 1.13 ·10¹¹
for n log₁₀ ( 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 2²ⁿ?

As for the 3.6·10² 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·10² Honestly thought it was 36·10² 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 ·10¹² above.

 

[haruspex]

The Lambert-W function as part of the solution sounds a bit too complicated for a day 1 homework problem

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.

 

[Ray Vickson]

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

n = 1.13 ·10¹¹
for n log₁₀ ( 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 2²ⁿ?

As for the 3.6·10² 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·10² Honestly thought it was 36·10² 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 ·10¹² above.

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.

 

[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

 

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

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.