Double check my calculations?

K

KateS

New member
Joined
Jun 1, 2013
Messages
6
I am looking at algorithms and am given the maximum size of a problem solvable in one second is n = 100 million. I need to calculate the maximum problem size that can be completed in one second using different running times. I had issues calculating some of them, so I was looking for some help if I had gone wrong, thanks: n = 100 million, log(n) = 10, 100n = 1 million, n log(n) = 10, n^2 = 10 thousand, n^3 = 464, 2^n = 1.41
 
KateS said:
I am looking at algorithms and am given the maximum size of a problem solvable in one second is n = 100 million. I need to calculate the maximum problem size that can be completed in one second using different running times. I had issues calculating some of them, so I was looking for some help if I had gone wrong, thanks: n = 100 million, log(n) = 10, 100n = 1 million, n log(n) = 10, n^2 = 10 thousand, n^3 = 464, 2^n = 1.41
Click to expand...
Please read Read Before Posting.

This problem as stated makes no sense to me. What does the actual problem say?

Furthermore, it is hard to help you with wherever you are stuck in your work if you do not show us your work. If you cannot even get started, we can give you some hints on that if we knew what the problem actually says.

What course are you taking, a CS course on algorithms? Have you studied algebra? We have no clue what type of answer will work for YOU if we know nothing about you.
 
JeffM said:
Please read Read Before Posting.

This problem as stated makes no sense to me. What does the actual problem say?

Furthermore, it is hard to help you with wherever you are stuck in your work if you do not show us your work. If you cannot even get started, we can give you some hints on that if we knew what the problem actually says.

What course are you taking, a CS course on algorithms? Have you studied algebra? We have no clue what type of answer will work for YOU if we know nothing about you.
Click to expand...

For some reason in my initial post new lines were not working, they appear to be now? Anyway, I am working on a math question for an algorithm topic. This is a high level question where we are asked what the maximum problem size is for different algorithm running times that a machine could perform per second.

For a base case we are given that an algorithm that has a running time of n, 100 million is the maximum size of the problem that can be solved in a second

n = 100 million

So I have calculated the following and I am not sure how correct my math is (I have listed how I calculated the first couple to show what I mean):

100n = 1 million (by dividing 100 million by 100)
n^2 = 10 thousand (by calculating the square root of 100 million)
log(n) = 10
n log(n) = 10
n^3 = 464
2^n = 1.41
 
Hi KateS:


How is "algorithm running time" measured, and how do you determine it?


What are the units on n = 100 million?

Cheers :cool:

PS: If you divide one side of an equation by 100, you need to divide the other side by 100, too.

n = 100 million

n/100 = 100 million/100

1/100th of n = 1 million
 
mmm4444bot said:
Hi KateS:


How is "algorithm running time" measured, and how do you determine it?


What are the units on n = 100 million?

Cheers :cool:

PS: If you divide one side of an equation by 100, you need to divide the other side by 100, too.

n = 100 million

n/100 = 100 million/100

1/100th of n = 1 million
Click to expand...

100n = 1 million (by dividing 100 million by 100)
n^2 = 10 thousand (by calculating the square root of 100 million)
log(n) = 10
n log(n) = 10
n^3 = 464
2^n = 1.41

So what I mean by the above is that the first values are the running time of the algorithm and the value after the equal sign is what I have calculated is the maximum problem size. So, for the first one, the running time of this algorithm is 100*n and given n = 100 million, to get the maximum size of the problem that could be performed, I divide by a million and get the result to be 1 million. That is one of the results I am certain about, where as some of the others I am not sure if I have calculated n correctly.

I hope that helps clear up what I meant.
 
Are you able to answer either of the questions, in my previous reply?
 
Last edited:
KateS said:
I divide by a million and get the result to be 1 million. That is one of the results I am certain about
Click to expand...

That's a misstatement, yes? You divided by 100.





Okay -- I'm still trying to understand the exercise. From what class does this exercise come?





For run time n, maximum problem size is 100 million.


For run time 100n, maximum problem size is _____.


You filled in the blank with 1 million.


100n is bigger than n. I would expect the maximum problem size to increase, if the run time increases, so there's something basic about how run time and the size are related that I'm not understanding.


How did you know to divide the problem size by 100, when you saw that n changed to 100n?
 
mmm4444bot said:
That's a misstatement, yes? You divided by 100.
Click to expand...

Your right.


mmm4444bot said:
Okay -- I'm still trying to understand the exercise. From what class does this exercise come?
Click to expand...

Introductory algorithms class.



mmm4444bot said:
For run time n, maximum problem size is 100 million.


For run time 100n, maximum problem size is _____.


You filled in the blank with 1 million.


100n is bigger than n. I would expect the maximum problem size to increase, if the run time increases, so there's something basic about how run time and the size are related that I'm not understanding.


How did you know to divide the problem size by 100, when you saw that n changed to 100n?
Click to expand...

When the running time of the algorithm is 100*n, that means it is 100 times slower than the algorithm that works in n time. So in the same amount of time 100 times less problems could be solved.
 
Okay -- so, this exercise kinda looks like inverse operations.

To get from 100n back to n, you divided by 100.

To get from n^2 back to n, you took the square root.

To get from n^3 back to n, you took the cube root.

Those steps match your posted results.

To get from 2^n back to n, we take the base-2 logarithm of 2^n:

log2(2^n) = n*log2(2) = n*1 = n

log2(100 million) = 26.575 ... not sure whether you're rounding or truncating

To get from log10(n) back to n, by the definition of logarithms, we raise 10 to the power of log10(n).

But 10^(100 million) is VERY large, large enough for me to wonder whether something other than inverses is involed. Does such a large number make sense to you?
 
mmm4444bot said:
Okay -- so, this exercise kinda looks like inverse operations.

To get from 100n back to n, you divided by 100.

To get from n^2 back to n, you took the square root.

To get from n^3 back to n, you took the cube root.

Those steps match your posted results.

To get from 2^n back to n, we take the base-2 logarithm of 2^n:

log2(2^n) = n*log2(2) = n*1 = n

log2(100 million) = 26.575 ... not sure whether you're rounding or truncating

To get from log10(n) back to n, by the definition of logarithms, we raise 10 to the power of log10(n).

But 10^(100 million) is VERY large, large enough for me to wonder whether something other than inverses is involed. Does such a large number make sense to you?
Click to expand...

Thanks, logarithms are still a bit tricky for me. Yes, a large number for log(n) makes sense.
 
KateS said:
I am looking at algorithms and am given the maximum size of a problem solvable in one second is n = 100 million. I need to calculate the maximum problem size that can be completed in one second using different running times. I had issues calculating some of them, so I was looking for some help if I had gone wrong, thanks: n = 100 million, log(n) = 10, 100n = 1 million, n log(n) = 10, n^2 = 10 thousand, n^3 = 464, 2^n = 1.41
Click to expand...
I don't understand what you are asking. If n= 100 million then ln(n) is certainly NOT 10 and 100n is NOT 1 million.
 
Kate's not using the equal signs to show equality; she's using them to show associations. (That had me confused, too.)
 
I think this is a HW from computer science class - involving Big_O notation.
 
You must log in or register to reply here.
Top