3 ms·
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
by pjscott 16y ago
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.
- 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.