5 ms·

I wonder what's the efficiency of this algorithm in O notation on average.

by Mahn 12y ago

deleted 12y ago
[deleted]
- statusgraph 12y ago
  Not quite. Big-O creates an -upper bound-. It could be the upper bound of the best case, the average, or the worst case. (So, for example, one can say quicksort has worst case performance O(n^2) but an expected performance of O(n log n))
- btilly 12y ago
  Big-O notation refers to the worst case runtime of an algorithm. I have no idea where this misconception comes from. Big-O notation is a type of bound on a function's growth rate. That function can represent anything. Best case performance, worst case performance, average case performance, memory usage, how many times you are likely to phone someone while you wait, etc. The standard example showing this is that hash lookups are O(1) or O(n) depending on whether you are asking about the average case or the worst case.
  - wzsddtc 12y ago
    that's not 100% true as well, you got omega and theta and others as well for the other cases. Edit: See http://stackoverflow.com/questions/471199/what-is-the-difference-between-%CE%98n-and-on http://stackoverflow.com/questions/471199/what-is-the-differ...
    - jholman 12y ago
      btilly's comment is exactly correct (though obviously not a complete explanation of everything). The S.O. link you posted contains an Accepted Answer which is also exactly correct, and happens to agree exactly with btilly. I don't know what you think you're saying, or what you think that SO link supports. But it is NOT the case that "big O is worst-case", nor is it the case that the variants like little-o/big-theta/big-omega/etc have anything to do with best/worst/average case. The relevant sense of "upper bound" is not some kind of subtle synonym for "worst case".
coreyja 12y ago
As tansey said Big-O for the worst case would be O(inf), Best case is O(1), if n is the length of the list, because if the sort returns the speed is independent of the size of the list. The average case is a little harder, but based on the 140 character limit someone else mentioned, I would say that the average case would be O(inf) cause on average it probably wouldn't correctly sort the list.
- pliny 12y ago
  The speed is definitely not independent of the size since you still have to write a string of size O(n).
moe 12y ago
The probability of the original input list being in the exact order it's in is 1/(n!). If that's the order you wanted then the algorithm might very well approach O(0).
archagon 12y ago
It's O(whatever algorithm the responder uses), plus a HUUUGE constant for latency and wrong answers.

I wonder what's the efficiency of this algorithm in O notation on average.

by Mahn 12y ago

I wonder what's the efficiency of this algorithm in O notation on average.

deleted 12y ago

[deleted]

statusgraph 12y ago
Not quite. Big-O creates an -upper bound-. It could be the upper bound of the best case, the average, or the worst case. (So, for example, one can say quicksort has worst case performance O(n^2) but an expected performance of O(n log n))
btilly 12y ago
Big-O notation refers to the worst case runtime of an algorithm. I have no idea where this misconception comes from. Big-O notation is a type of bound on a function's growth rate. That function can represent anything. Best case performance, worst case performance, average case performance, memory usage, how many times you are likely to phone someone while you wait, etc. The standard example showing this is that hash lookups are O(1) or O(n) depending on whether you are asking about the average case or the worst case.
- wzsddtc 12y ago
  that's not 100% true as well, you got omega and theta and others as well for the other cases. Edit: See http://stackoverflow.com/questions/471199/what-is-the-difference-between-%CE%98n-and-on http://stackoverflow.com/questions/471199/what-is-the-differ...
  - jholman 12y ago
    btilly's comment is exactly correct (though obviously not a complete explanation of everything). The S.O. link you posted contains an Accepted Answer which is also exactly correct, and happens to agree exactly with btilly. I don't know what you think you're saying, or what you think that SO link supports. But it is NOT the case that "big O is worst-case", nor is it the case that the variants like little-o/big-theta/big-omega/etc have anything to do with best/worst/average case. The relevant sense of "upper bound" is not some kind of subtle synonym for "worst case".

coreyja 12y ago

As tansey said Big-O for the worst case would be O(inf), Best case is O(1), if n is the length of the list, because if the sort returns the speed is independent of the size of the list. The average case is a little harder, but based on the 140 character limit someone else mentioned, I would say that the average case would be O(inf) cause on average it probably wouldn't correctly sort the list.

pliny 12y ago
The speed is definitely not independent of the size since you still have to write a string of size O(n).

moe 12y ago

The probability of the original input list being in the exact order it's in is 1/(n!). If that's the order you wanted then the algorithm might very well approach O(0).

archagon 12y ago

It's O(whatever algorithm the responder uses), plus a HUUUGE constant for latency and wrong answers.