News for hackers. Stuff that matters.

A comment on Fallacies of Distributed Computing. Parent comment

Re:Fallacies of Distributed Computing by billswift on Thursday April 21, 2011 @02:17PM (#2471660)
Big O can be used to represent worst-case behavior, but it can be, and is used also for average-case. And no, it is not a misuse of the notation - it is legitimately used for both (also for best-case, but I have never heard of anybody actually bothering with that). Just be sure to understand which is being talked about.
[ Parent | on HN ]
Re:Fallacies of Distributed Computing by pjscott on Thursday April 21, 2011 @02:26PM (#2471694)
Okay, this is a subtle point, but you're right. Big-O notation describes an asymptotic upper bound on any function. If that function is average run time, then that's perfectly kosher. Actually establishing what this means, though, is a bit trickier, and something people often mess up.
[ Parent | on HN ]
Re:Fallacies of Distributed Computing by arethuza on Thursday April 21, 2011 @02:47PM (#2471791)
I don't think it's a subtle point at all - Big-O is not inherently anything to do with worst case time complexity of algorithms, it is a general relationship between functions.
[ Parent | on HN ]
Re:Fallacies of Distributed Computing by alecco on Thursday April 21, 2011 @02:54PM (#2471840)
Also, beware if pre-asymptotic behavior is significant.
[ Parent | on HN ]