4 ms·

I'm confused by what the article is saying about the meaning of Big-O... FTA: > Misconception 4: Big-O Is About Worst Case But it is. Big-O is an upper bound

by B-Con 14y ago

I'm confused by what the article is saying about the meaning of Big-O... FTA: > Misconception 4: Big-O Is About Worst Case But it is. Big-O is an upper bound which is by definition a maximum (aka, "worst") case. "f = O(n)" means that at worst "f" will perform linear work, not that it is expected to. He gave this definition himself in the very beginning. Then he states Misconception #4 and he says that Big-O is not about worst case. He doesn't sound like he is implying that programmers casually use Big-O this way, he seems to be saying this is how the real definition actually is. But it isn't.

tylerneylon 14y ago
Upper bound != worst case, though I can see why the language is confusing. When we have a timing function f(n) we pretend f has one input, which is n = the size of the input to the algorithm. In reality, it's actually more like f(n, m) where m = a parameter specifying the _exact_ input to the algorithm. (Example: sorting algorithms have many possible input lists of length n.) So when we write f(n) = O(g(n)), we are trying to make two simplifications: (1) Simplify away the actual input, replaced by only the _size_ of the input; and (2) simplify the actual function f to something that describes f but is much simpler. I will make up an artificial example that is not perfect but is useful to explain the ideas. Suppose for any input size n we have parameters m in the range [-n-sin(n), n+sin(n)] and the exact timing function f(n, m) = n + sin(n) + m Then the first simplification is to determine how to ignore m. We could pick out the best m for n (the smallest f(n, m) for a fixed n), pick out the worst m, or take the average over all m. This is best-case, average-case, and worst-case complexity. For this function, we have: f(n) = 0 [best case] f(n) = n + sin(n) [avg case] f(n) = 2(n + sin(n)) [worst case] Then we could get an upper bound on _any_ of these. f(n) = O(1) [best case] f(n) = O(n) [avg and worst case, not always the same, but they are the same in this example] If we wanted a lower bound, we could say that f(n) = Omega(n) [avg & worst case] because f(n) >= n - 1 for all n (in general there could be more room for flexibility on the right-hand side, but it's not needed in this example). The point here is that step 1 chooses a simplification across input instances, that we call worse case or average case, etc; and step 2 chooses a simplification in how to write down the function f(n), and this is what we call an upper bound for big-oh, or for theta, both an upper and lower bound.
- B-Con 14y ago
  Yes. Big-O is the worst case for the input, not for the algorithm. If the input is the expected average, then its Big-O is the upper-bound/worst-case for the average. But if the input is the worst case or just the algorithm itself, its Big-O will be an upper-bound/worst-case for the entire algorithm. In other words, the original article's point should have been about vocabulary. Big-O is about worst-case, but sometimes it's implied that the Big-O analysis is about the algorithm's average case, not the algorithm's worst case.
btilly 14y ago
Let me try to say it simply. Big-O is an upper bound on the growth of a function. The function being bounded can (per his item #3) represent anything of interest. In practice it is common for the function to be the average running time of an algorithm. In this case the upper bound on the growth of that function says nothing about how badly the algorithm might perform upon rare occasion. His example is quicksort. A naive quicksort sorts n things in on average O(n log(n)) time, but if presented with an already sorted set will take time O(n²). Another one that I'd offer is a hash. The average lookup time for an element in a standard hash is O(1). The worst case lookup time is O(n). If I am trying to figure out how long a batch job is that has to do a ton of work, including a lot of hash lookups, I care about the average lookup time, because I do not expect to encounter the worst case.) If I am trying to construct a hard real-time system that absolutely must complete an operation in fixed time, despite 1000 trial runs that found the hash to be fast enough, the slow worst case scenario should scare me into using a more predictable data structure.
- B-Con 14y ago
  > Big-O is an upper bound on the growth of a function. The function being bounded can (per his item #3) represent anything of interest. > In practice it is common for the function to be the average running time of an algorithm. In other words, Big-O is the worst-case of the input. You do the complexity analysis and then assign it to a Big-O class, the Big-O class represents the worst-case for that given analysis. If you analyze the average, its Big-O class will be the worst-case/upper-bound of the average and you obviously can't expect it to say anything about the actual full algorithm's worst case scenario because, well, you didn't analyze the algorithm's worst-case scenario. Big-O is worst-case, you just have to know what it's the worst case of. If the input is just "here is the quicksort algorithm", then Big-O would be the upper-bound for the algorithm itself, aka the worst case for the algorithm, namely O(n²). This seems to be just an issue of convention, does "Big-O" refer to the upper bound on the algorithm or on the average algorithm performance? That's been discussed elsewhere, but it seems like programmers imply the average while the strict definition does not. So my point was that the original article should have just said to be careful about vocabulary, not asserted that Big-O isn't about worst case, since it is.

by B-Con 14y ago

tylerneylon 14y ago

Upper bound != worst case, though I can see why the language is confusing. When we have a timing function f(n) we pretend f has one input, which is n = the size of the input to the algorithm. In reality, it's actually more like f(n, m) where m = a parameter specifying the _exact_ input to the algorithm. (Example: sorting algorithms have many possible input lists of length n.) So when we write f(n) = O(g(n)), we are trying to make two simplifications: (1) Simplify away the actual input, replaced by only the _size_ of the input; and (2) simplify the actual function f to something that describes f but is much simpler. I will make up an artificial example that is not perfect but is useful to explain the ideas. Suppose for any input size n we have parameters m in the range [-n-sin(n), n+sin(n)] and the exact timing function f(n, m) = n + sin(n) + m Then the first simplification is to determine how to ignore m. We could pick out the best m for n (the smallest f(n, m) for a fixed n), pick out the worst m, or take the average over all m. This is best-case, average-case, and worst-case complexity. For this function, we have: f(n) = 0 [best case] f(n) = n + sin(n) [avg case] f(n) = 2(n + sin(n)) [worst case] Then we could get an upper bound on _any_ of these. f(n) = O(1) [best case] f(n) = O(n) [avg and worst case, not always the same, but they are the same in this example] If we wanted a lower bound, we could say that f(n) = Omega(n) [avg & worst case] because f(n) >= n - 1 for all n (in general there could be more room for flexibility on the right-hand side, but it's not needed in this example). The point here is that step 1 chooses a simplification across input instances, that we call worse case or average case, etc; and step 2 chooses a simplification in how to write down the function f(n), and this is what we call an upper bound for big-oh, or for theta, both an upper and lower bound.

B-Con 14y ago
Yes. Big-O is the worst case for the input, not for the algorithm. If the input is the expected average, then its Big-O is the upper-bound/worst-case for the average. But if the input is the worst case or just the algorithm itself, its Big-O will be an upper-bound/worst-case for the entire algorithm. In other words, the original article's point should have been about vocabulary. Big-O is about worst-case, but sometimes it's implied that the Big-O analysis is about the algorithm's average case, not the algorithm's worst case.

btilly 14y ago

Let me try to say it simply. Big-O is an upper bound on the growth of a function. The function being bounded can (per his item #3) represent anything of interest. In practice it is common for the function to be the average running time of an algorithm. In this case the upper bound on the growth of that function says nothing about how badly the algorithm might perform upon rare occasion. His example is quicksort. A naive quicksort sorts n things in on average O(n log(n)) time, but if presented with an already sorted set will take time O(n²). Another one that I'd offer is a hash. The average lookup time for an element in a standard hash is O(1). The worst case lookup time is O(n). If I am trying to figure out how long a batch job is that has to do a ton of work, including a lot of hash lookups, I care about the average lookup time, because I do not expect to encounter the worst case.) If I am trying to construct a hard real-time system that absolutely must complete an operation in fixed time, despite 1000 trial runs that found the hash to be fast enough, the slow worst case scenario should scare me into using a more predictable data structure.

B-Con 14y ago
> Big-O is an upper bound on the growth of a function. The function being bounded can (per his item #3) represent anything of interest. > In practice it is common for the function to be the average running time of an algorithm. In other words, Big-O is the worst-case of the input. You do the complexity analysis and then assign it to a Big-O class, the Big-O class represents the worst-case for that given analysis. If you analyze the average, its Big-O class will be the worst-case/upper-bound of the average and you obviously can't expect it to say anything about the actual full algorithm's worst case scenario because, well, you didn't analyze the algorithm's worst-case scenario. Big-O is worst-case, you just have to know what it's the worst case of. If the input is just "here is the quicksort algorithm", then Big-O would be the upper-bound for the algorithm itself, aka the worst case for the algorithm, namely O(n²). This seems to be just an issue of convention, does "Big-O" refer to the upper bound on the algorithm or on the average algorithm performance? That's been discussed elsewhere, but it seems like programmers imply the average while the strict definition does not. So my point was that the original article should have just said to be careful about vocabulary, not asserted that Big-O isn't about worst case, since it is.