-2

2nd year computer science student here. In class we are covering asymptotic notation, sorting algorithms and such. I need some help understanding asymptotic notation and how the values relate to one another. I have been at it for a little while but I can't seem to arrive at a reasonable conclusion. I imagine the answer is something simple but it eludes me. My professor provided us with a hand-out that goes into pretty good detail about asymptotic notation and how it is used.

So, the hand out asks the following questions:

What is the distinction between Big-O and Big-theta asymptotic performance?

My conclusions from the hand-out are:

-Big-O performance means an algorithm can finish early and that the asymptotic performance is the worst case scenario.

-Big-Theta performance means an algorithm cannot finish early and that the asymptotic performance is the best case scenario.

If these assumptions are incorrect can someone sesame street it for me?

-and-

A wood-chuck requires 20 seconds to chuck 60 chucks of wood, and the wood-chuck’s wood-chucking algorithm has temporal asymptotic performance Theta(n^2). How much wood could this wood-chuck chuck (if a wood-chuck could chuck wood) in five minutes?

I understand that since the algorithm is n^2 we can expect that the amount of time it takes to chuck more and more wood is exponential. I don't however see how we can find the amount of wood given in 5 minutes. I feel like I am over-thinking this and the answer is something simple. Any help would be greatly appreciated.

Greg Levy
  • 1
  • Hint: If you double the number of items, the O(n^2) algorithm will take four times as long to complete. – Jim Mischel Nov 13 '16 at 05:52
  • I see, so would the equation be O(2n^2) = 80seconds, O(4n^2) = 160seconds, and so on? If so, we have O(an^2) = 300seconds, where a is some constant value. So if I can solve for 'a' I get the number of woods chucked lol. Is this correct? – Greg Levy Nov 13 '16 at 06:23
  • Possible duplicate of [What is a plain English explanation of "Big O" notation?](http://stackoverflow.com/questions/487258/what-is-a-plain-english-explanation-of-big-o-notation) – xenteros Nov 14 '16 at 07:06

1 Answers1

0

If you know that you have an O(n^2) algorithm and you can do X units of work in Y seconds, then you can do 2X units of work in approximately 4Y seconds. You can do 4X units of work in approximately 16Y seconds.

Or, the amount of work you can do in 16*Y seconds is equal to X*sqrt(16).

So the amount of work you can do in Z seconds is X*sqrt(Z). The square root of 15 is approximately 3.873, meaning you can do 60*3.873, or 232.46 units of work in 15 seconds.

It's important to remember, though, that you're working with approximations here. Asymptotic "math" doesn't give exact numbers. Were I doing this exercise in real life (and I have done something quite similar), I'd estimate that I could do about four times as much work in 300 seconds as I did in 20 seconds, because 300 is approximately 16 times as much time.

So my answer to this question would be "approximately 240 chucks."

Jim Mischel
  • 131,090
  • 20
  • 188
  • 351