2 ms·

To put names to what you're asking for: best-case, average-case and worst-case analysis. All are valid ways to characterize algorithms.

kadoban 8y ago
Average-case can be quite an odd beast. You have to be careful what you are averaging over -- what distribution you're assuming in the analysis. For example for quicksort, if you implement it such that it always pivots on the first element of the range to be sorted, that could be average-case O(n lg n) if I consider all possible orderings of the inputs of the given size, but if I usually call it with an almost sorted array, that's not the average behavior I'm going to see by any means. So in most cases it ends up being a pretty leaky and dangerous contract that your function is providing, with average-case analysis. You have to know deep details of how it's working. An often better way to go, when it's possible, is to use expected-time. So again using quicksort as an example, this would mean the algorithm randomly chooses a pivot in the given range. The difference now is, the worst-case is still O(n^2), but there's no input I can give it (accidentally or intentionally) that will trigger that behavior, I'd have to get insanely unlucky for that to happen on a large input.
- scott_s 8y ago
  I almost made the same point, but I stopped because I was hesitant to get into the cases where one can do an average-case analysis without assuming any distributions: when you're doing analysis of a particular operation being called a bunch of times, versus once. In such cases, average-case can yield amortized analysis which still makes no assumption of the input distribution. I'm co-author on a paper which does that: https://www.scott-a-s.com/files/debs2017_daba.pdf https://www.scott-a-s.com/files/debs2017_daba.pdf. In that work, we present a sliding window aggregation algorithm for worst-case constant time, but we compare against ones that are average-case constant time. The average-case constant algorithms are better on throughput, but worst-case constant is better on latency.

kadoban 8y ago

Average-case can be quite an odd beast. You have to be careful what you are averaging over -- what distribution you're assuming in the analysis. For example for quicksort, if you implement it such that it always pivots on the first element of the range to be sorted, that could be average-case O(n lg n) if I consider all possible orderings of the inputs of the given size, but if I usually call it with an almost sorted array, that's not the average behavior I'm going to see by any means. So in most cases it ends up being a pretty leaky and dangerous contract that your function is providing, with average-case analysis. You have to know deep details of how it's working. An often better way to go, when it's possible, is to use expected-time. So again using quicksort as an example, this would mean the algorithm randomly chooses a pivot in the given range. The difference now is, the worst-case is still O(n^2), but there's no input I can give it (accidentally or intentionally) that will trigger that behavior, I'd have to get insanely unlucky for that to happen on a large input.

scott_s 8y ago
I almost made the same point, but I stopped because I was hesitant to get into the cases where one can do an average-case analysis without assuming any distributions: when you're doing analysis of a particular operation being called a bunch of times, versus once. In such cases, average-case can yield amortized analysis which still makes no assumption of the input distribution. I'm co-author on a paper which does that: https://www.scott-a-s.com/files/debs2017_daba.pdf https://www.scott-a-s.com/files/debs2017_daba.pdf. In that work, we present a sliding window aggregation algorithm for worst-case constant time, but we compare against ones that are average-case constant time. The average-case constant algorithms are better on throughput, but worst-case constant is better on latency.