programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
• Campbell Ritchie
• Ron McLeod
• Junilu Lacar
• Paul Clapham
• Liutauras Vilda
Sheriffs:
• Jeanne Boyarsky
• Rob Spoor
• Bear Bibeault
Saloon Keepers:
• Tim Moores
• Tim Holloway
• Piet Souris
• Carey Brown
• Stephan van Hulst
Bartenders:
• Frits Walraven
• fred rosenberger
• salvin francis

# Effect of Doubling the Size on Running Time

Ranch Hand
Posts: 373
• Number of slices to send:
Optional 'thank-you' note:
How do I do the last column of this worksheet? I know proportions is not correct.
big-o.jpg

Marshal
Posts: 16435
271
• 1
• Number of slices to send:
Optional 'thank-you' note:
The second column tells you what to do

Ana Smith
Ranch Hand
Posts: 373
• Number of slices to send:
Optional 'thank-you' note:
For the second one is the answer, 2^37?

Ana Smith
Ranch Hand
Posts: 373
• Number of slices to send:
Optional 'thank-you' note:
If it is then I'm doing it right.

Junilu Lacar
Marshal
Posts: 16435
271
• Number of slices to send:
Optional 'thank-you' note:

Ana Smith wrote:For the second one is the answer, 2^37?

Can you explain why you think so and how that reconciles with what the 2nd column says?

Ana Smith
Ranch Hand
Posts: 373
• Number of slices to send:
Optional 'thank-you' note:
So what I did is log500(log base 2 500)=8
and then 1000 will take 37 ms and logN(log base 2 N) =37 which results in N=2^37. Is this correct

Junilu Lacar
Marshal
Posts: 16435
271
• Number of slices to send:
Optional 'thank-you' note:

Ana Smith
Ranch Hand
Posts: 373
• Number of slices to send:
Optional 'thank-you' note:
So is it 2^37 +1

Junilu Lacar
Marshal
Posts: 16435
271
• Number of slices to send:
Optional 'thank-you' note:
2^37 is an awfully large number. What is the growth characteristic of O(log N)? Does 3ms to 2^37+1 conform to that?

Ana Smith
Ranch Hand
Posts: 373
• Number of slices to send:
Optional 'thank-you' note:
I just don't know how to do it. If you can give me the procedure to the second problem then I will understand how to do the rest.

Junilu Lacar
Marshal
Posts: 16435
271
• Number of slices to send:
Optional 'thank-you' note:
Try the third one first. That's easier.

Junilu Lacar
Marshal
Posts: 16435
271
• Number of slices to send:
Optional 'thank-you' note:

Ana Smith
Ranch Hand
Posts: 373
• Number of slices to send:
Optional 'thank-you' note:
Is it 6 seconds for the third one?

Ana Smith
Ranch Hand
Posts: 373
• Number of slices to send:
Optional 'thank-you' note:
I got 1 for the first one.

Junilu Lacar
Marshal
Posts: 16435
271
• Number of slices to send:
Optional 'thank-you' note:

Ana Smith wrote:Is it 6 seconds for the third one?

No. Either you're not reading the header of the third column carefully or you're not understanding it. Read it again.

Ana Smith
Ranch Hand
Posts: 373
• Number of slices to send:
Optional 'thank-you' note:
7?

Junilu Lacar
Marshal
Posts: 16435
271
• Number of slices to send:
Optional 'thank-you' note:

Ana Smith wrote:I got 1 for the first one.

That is incorrect

Ana Smith
Ranch Hand
Posts: 373
• Number of slices to send:
Optional 'thank-you' note:
Wait are we supposed to double the data and then do the fourth column?

Junilu Lacar
Marshal
Posts: 16435
271
• Number of slices to send:
Optional 'thank-you' note:

Ana Smith wrote:7?

Ana Smith
Ranch Hand
Posts: 373
• Number of slices to send:
Optional 'thank-you' note:
Can you show me how to do one of them so I can easily understand the rest?

Junilu Lacar
Marshal
Posts: 16435
271
• Number of slices to send:
Optional 'thank-you' note:
The second column says for O(1) it will remain unchanged. So if n=500 take 3ms and it remains unchanged for n=1000 then what is the time (unchanged)?

Junilu Lacar
Marshal
Posts: 16435
271
• Number of slices to send:
Optional 'thank-you' note:
The "3ms" in the third column header stands for 3 milliseconds

Bartender
Posts: 1204
22
• 1
• Number of slices to send:
Optional 'thank-you' note:
For the O(log N) row...  Increased by 1 what?  ms?  s? minute?

How to do these in general:

1. Create an equation that sets the known time equal to an unknown coefficient times the big O expression with the known value for N substitutes in.
2. Solve that for the unknown coefficient.
3. Use that with the other known value for N to get the (reasonable estimate of) the time for that N value.

Let's try the O(N) row.  The known N is 500 and the known time is 3 ms.

Step 1: Let's call the unknown coefficient "c":  3ms = c * 500
Step 2: c = 3ms / 500.
Step 3: t = (3ms/500) * 1000, so t = 6ms.

Now do that for the other rows.

For the O(log N) row, the equation for step 1 would be c * log(500) = 3 ms.

You do the rest.

Ana Smith
Ranch Hand
Posts: 373
• Number of slices to send:
Optional 'thank-you' note:
Thank you for both of your help!

Junilu Lacar
Marshal
Posts: 16435
271
• Number of slices to send:
Optional 'thank-you' note:

Ryan McGuire wrote:For the O(log N) row...  Increased by 1 what?  ms?  s? minute?

I would assume the student is expected to apply critical thinking here as well. Understanding the shape of the growth curve of O(log N) is important. If n = 500 is completed in 3 ms, is it really reasonable to think that n = 1000 would take 1 whole second longer, much less 1 whole minute longer?

Junilu Lacar
Marshal
Posts: 16435
271
• Number of slices to send:
Optional 'thank-you' note:
The first and third ones are quite straightforward.

O(1) -> unchanged from O(500) to O(1000). So if 3ms is unchanged, then...

O(N) -> is doubled when N is doubled. So since O(500) is 3ms, then double that gives you...  (?) ms -- I hope we're not confused by what "doubled" means.

Ryan McGuire
Bartender
Posts: 1204
22
• Number of slices to send:
Optional 'thank-you' note:

Junilu Lacar wrote:

Ryan McGuire wrote:For the O(log N) row...  Increased by 1 what?  ms?  s? minute?

I would assume the student is expected to apply critical thinking here as well. Understanding the shape of the growth curve of O(log N) is important. If n = 500 is completed in 3 ms, is it really reasonable to think that n = 1000 would take 1 whole second longer, much less 1 whole minute longer?

I 100% percent agree that some critical thinking is needed.  My point is that "increased by 1" is meaningless exactly because it doesn't indicate what the units are.  In fact, if you work through the math, the amount that is added for doubling of the data set size from 500 to 1000 is considerably less than 1 ms.  Once you know what that additional time is when increasing the data set size to 1000, you can easily work out the expected run times for data set sizes 2000, 4000, 8000, etc.

Junilu Lacar
Marshal
Posts: 16435
271
• Number of slices to send:
Optional 'thank-you' note:
I dont think the point of the exercise is about getting precise measurements. Big O is about worst case. What would O(250), O(125), and O(62) be then? Are we really concerned about what those exact numbers are in this exercise?

Ryan McGuire
Bartender
Posts: 1204
22
• Number of slices to send:
Optional 'thank-you' note:

Junilu Lacar wrote:I dont think the point of the exercise is about getting precise measurements. Big O is about worst case. What would O(250), O(125), and O(62) be then? Are we really concerned about what those exact numbers are in this exercise?

I would say that the point of the exercise is to give the student an idea of how big O notation works.  If a bit of notation in the table is meaningless, then it fails at supporting the point of the exercise.

I would change "increased by 1" to "increased by a constant amount".  At least that would be correct, even though you would still have to do the math to figure out what that "constant amount" is.

Junilu Lacar
Marshal
Posts: 16435
271
• Number of slices to send:
Optional 'thank-you' note:
I won't presume to know what the author of that exercise was thinking but in my opinion, he or she was going for a basic understanding of the shape of each growth curve.

For O(log N), the growth in time is very slow in relation to the growth in N, so when the second column says "increased by 1" and the header in the third column says "N=500 is 3ms, then N=1000 is __ ms" then I think, given what the student should have learned about the growth of O(log N), it would be reasonable to answer "3ms + 1ms => 4ms (at worst)" and that further doubling, given the assumption that each doubling only "increases (work) by 1," then O(2000) => 5ms, O(4000) => 6ms, O(8000) => 7ms, all of which will be "at worst" and which if plotted out would reasonably be expected to approximate the shape of an O(log N) curve.

If you've ever tried measuring performance of algorithms, you probably know that you won't get the same exact measurements from run to run. There will be some variance of the exact numbers but the trends as N increases will follow a predictable pattern. Big O is not meant to be a formula for exact measurements but rather an indication of the shape of the growth of the curve. Formally, "it describes the limiting behavior of a function when the argument tends towards a particular value or infinity"

Ryan McGuire
Bartender
Posts: 1204
22
• Number of slices to send:
Optional 'thank-you' note:
I guess it's just a question of degree.  You agreed with me that using a unit of one second or one minute is unreasonable, even though using either of those units would also yield a perfectly fine log curve.  My point is that using a unit of ms, which is still off by a factor of three, is also unreasonable.  However, I will concede that being off by a factor of 3 is certainly more reasonable than being off by a factor of 3000 or 180,000

Junilu Lacar
Marshal
Posts: 16435
271
• Number of slices to send:
Optional 'thank-you' note:

Ryan McGuire wrote:My point is that using a unit of ms, which is still off by a factor of three, is also unreasonable. However, I will concede that being off by a factor of 3 is certainly more reasonable than being off by a factor of 3000 or 180,000

I think it's a matter of choosing what's least unreasonable. I wouldn't get hung up on absolute numbers. Sure, if you extrapolate using seconds or minutes to N=2000, N=4000, N=8000 then the growth curve looks pretty much the same if you ignore the first plot point for t = 3ms. But the jump from O(500) => 3ms to O(1000) => 4000ms is not consistent with O(log N), much less jumping from 3ms to 60003ms so yeah, I would say the 3ms, 4ms, 5ms, 6ms, ... etc. growth is more representative of what you can expect an O(log N) curve to be shaped like, which is relatively flat and shallow curve.

Junilu Lacar
Marshal
Posts: 16435
271
• Number of slices to send:
Optional 'thank-you' note:
Here's a page that shows the shape of most (if not all) of the curves in that table: http://science.slc.edu/~jmarshall/courses/2002/spring/cs50/BigO/index.html

Ana Smith
Ranch Hand
Posts: 373
• Number of slices to send:
Optional 'thank-you' note:
If the data is doubled for O(N log N), why is the work done 2x<work<4x?

Junilu Lacar
Marshal
Posts: 16435
271
• Number of slices to send:
Optional 'thank-you' note:
You might want to follow the link I gave previously and look at the graph of n log n to see how doubling n affects the time.

Ana Smith
Ranch Hand
Posts: 373
• Number of slices to send:
Optional 'thank-you' note:
Thank you, also there is math associated with this so I want to learn how to prove that it is 2x<work<4x

Junilu Lacar
Marshal
Posts: 16435
271
• Number of slices to send:
Optional 'thank-you' note:
I believe you'll have to use limits. identify the lower and upper limits of N, then double the lower and halve the upper and see what N log N looks like for those two extremes. It has been too long since I've worked with limits so I'll leave it to you to figure that out.

Saloon Keeper
Posts: 4545
166
• Number of slices to send:
Optional 'thank-you' note:
A simple way (in Holland we speak of ' on its John Farmerswhistle') is to fill in 2N in the formula. If we then take the ratio, we get

(2Nlog(2N)) / Nlog (N), and after some reshuffling we get this ratio: 2 log(2) / log (N) + 2.

Since 0 < log (2) / log (N) < 1, we get a ratio that is between 2 and 4. But remember, these Big O thingies do not always mean much.

Ryan McGuire
Bartender
Posts: 1204
22
• Number of slices to send:
Optional 'thank-you' note:

Ana Smith wrote:Thank you, also there is math associated with this so I want to learn how to prove that it is 2x<work<4x

As far as the math goes, I'm going to point at my first post in this thread:  Use the known data set size and time to determine a coefficient, and then use that coefficient to estimate the time for the larger data set size.

c * 500 log(500) = 3ms
c * 500 * 2.7 = 3ms
c * 1350 = 3 ms
c = 0.0022 ms

0.0022 ms * 1000 * log(1000) = t
0.0022 ms * 3000 = t
6.66 ms = t

So yes... the time estimate for 1000 is between 2x and 4x the measured time for 500.

The worst part about this, as has been alluded to earlier, is that it provides an exact number for what is really an estimate at best, thus potentially giving you a false sense of security.  While the time is O(N logN) as N gets very large, there may well be some lower-order terms that may be contributing significantly to the run time at the 500-1000 range.

HOWEVER, I do think that working through the math will let you see what's contributing to the estimates.  As you can see above, for O(N logN), doubling N from 500 to 1000 will take the value that the coefficient above is multiplied by from 1350 to 3000 - i.e. a little more than double.  You can backtrack through the math I did above to see where those two numbers came from for the two data set sizes.

Marshal
Posts: 73244
332
• Number of slices to send:
Optional 'thank-you' note:
You can try...it comes to about 6.67. Near enough the same as you got.