5 ms·

I'm more interested in the lower, "average" (random input), sequential and empty set bounds as they tend get close, in certain instances (e.g. large memory spac

by consp 8y ago

I'm more interested in the lower, "average" (random input), sequential and empty set bounds as they tend get close, in certain instances (e.g. large memory space required, only efficient on ordered data etc), to the upper bound. If your algorithm for function is O(n^2) in theory but has an lower average bound of O(N log N) which almost always is used on your input data, it might be a good thing to sanitize the input and use it anyways (looking at you quicksort).

scott_s 8y ago
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.

by consp 8y ago

scott_s 8y ago

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.