5 ms·
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 legiti
by billswift 16y ago
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.
- pjscott 16y agoOkay, 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.
- arethuza 16y agoI 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.
- alecco 16y agoAlso, beware if pre-asymptotic behavior is significant.