News for hackers. Stuff that matters.
Re:Twitter Sort by Mahn on Tuesday January 13, 2015 @08:32PM (#8883730)
I wonder what's the efficiency of this algorithm in O notation on average.
Re:Twitter Sort by coreyja on Tuesday January 13, 2015 @08:52PM (#8883814)
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.
Re:Twitter Sort by pliny on Wednesday January 14, 2015 @03:08AM (#8884924)
The speed is definitely not independent of the size since you still have to write a string of size O(n).
Re:Twitter Sort by moe on Tuesday January 13, 2015 @09:01PM (#8883849)
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).
[deleted]
Re:Twitter Sort by btilly on Tuesday January 13, 2015 @08:53PM (#8883818)
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.

Re:Twitter Sort by wzsddtc on Wednesday January 14, 2015 @12:40AM (#8884518)
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-differ...

Re:Twitter Sort by jholman on Wednesday January 14, 2015 @08:55AM (#8886195)
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".

Re:Twitter Sort by statusgraph on Tuesday January 13, 2015 @08:44PM (#8883782)
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))
Re:Twitter Sort by archagon on Tuesday January 13, 2015 @09:10PM (#8883872)
It's O(whatever algorithm the responder uses), plus a HUUUGE constant for latency and wrong answers.