• Post Reply Bookmark Topic Watch Topic
  • New Topic
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 all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Liutauras Vilda
  • Junilu Lacar
  • Jeanne Boyarsky
  • Bear Bibeault
Sheriffs:
  • Knute Snortum
  • Devaka Cooray
  • Tim Cooke
Saloon Keepers:
  • Tim Moores
  • Stephan van Hulst
  • Tim Holloway
  • Ron McLeod
  • Carey Brown
Bartenders:
  • Paweł Baczyński
  • Piet Souris
  • Vijitha Kumara

Effect of Doubling the Size on Running Time

 
Ranch Hand
Posts: 331
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
How do I do the last column of this worksheet? I know proportions is not correct.
big-o.jpg
[Thumbnail for big-o.jpg]
 
Marshal
Posts: 14336
237
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
The second column tells you what to do
 
Ana Smith
Ranch Hand
Posts: 331
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
For the second one is the answer, 2^37?
 
Ana Smith
Ranch Hand
Posts: 331
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
If it is then I'm doing it right.
 
Junilu Lacar
Marshal
Posts: 14336
237
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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: 331
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 14336
237
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Read the header of the third column very carefully
 
Ana Smith
Ranch Hand
Posts: 331
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
So is it 2^37 +1
 
Junilu Lacar
Marshal
Posts: 14336
237
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 331
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 14336
237
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Try the third one first. That's easier.
 
Junilu Lacar
Marshal
Posts: 14336
237
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
And what's your answer for the first one?
 
Ana Smith
Ranch Hand
Posts: 331
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Is it 6 seconds for the third one?
 
Ana Smith
Ranch Hand
Posts: 331
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I got 1 for the first one.
 
Junilu Lacar
Marshal
Posts: 14336
237
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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: 331
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
7?
 
Junilu Lacar
Marshal
Posts: 14336
237
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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


That is incorrect
 
Ana Smith
Ranch Hand
Posts: 331
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Wait are we supposed to double the data and then do the fourth column?
 
Junilu Lacar
Marshal
Posts: 14336
237
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Ana Smith wrote:7?


Guessing is not going to help you.
 
Ana Smith
Ranch Hand
Posts: 331
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Can you show me how to do one of them so I can easily understand the rest?
 
Junilu Lacar
Marshal
Posts: 14336
237
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 14336
237
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
The "3ms" in the third column header stands for 3 milliseconds
 
Rancher
Posts: 1189
16
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 331
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thank you for both of your help!
 
Junilu Lacar
Marshal
Posts: 14336
237
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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: 14336
237
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Rancher
Posts: 1189
16
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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: 14336
237
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Rancher
Posts: 1189
16
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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: 14336
237
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Rancher
Posts: 1189
16
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 14336
237
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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: 14336
237
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 331
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
If the data is doubled for O(N log N), why is the work done 2x<work<4x?
 
Junilu Lacar
Marshal
Posts: 14336
237
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 331
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 14336
237
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Bartender
Posts: 3606
151
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Rancher
Posts: 1189
16
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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: 66189
250
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You can try...it comes to about 6.67. Near enough the same as you got.
 
The first person to drink cow's milk. That started off as a dare from this tiny ad:
Java file APIs (DOC, XLS, PDF, and many more)
https://products.aspose.com/total/java
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!