3 ms·

The average case for finding a value in an unsorted list is also O(n). Assuming the values you want are randomly distributed, on average you have to look at ha

The average case for finding a value in an unsorted list is also O(n). Assuming the values you want are randomly distributed, on average you have to look at half the list. Naively this sounds like O(n/2), but O(n/2) is actually the same as O(n) because you strip out the constant factor of 1/2.

baddox 13y ago
Of course. But it's also the worst case. I'm really just wondering if there's a "default" scenario that's being referred to when we just say "f(n) is in O(n)" or does it depend on context?
- anonymoushn 13y ago
  It depends on context. Generally if people fail to specify, they mean average case, as in "Quicksort takes O(n*lg n) time". There may even be some amortization shenanigans thrown in there, as in "list.append takes O(1) time".
- foobarbazqux 13y ago
  Quicksort is the exception, in my experience big-O usually refers to worst case running time as opposed to average case or expected running time. CLR(S) [1] sticks to worst case because 1) worst case is a guarantee; 2) the worst case can be frequent; 3) the average case is often roughly as bad as the worst case. This is a widely used textbook, so I generally assume a lot people follow its conventions. [1] https://mitpress.mit.edu/books/introduction-algorithms https://mitpress.mit.edu/books/introduction-algorithms (Introduction to Algorithms)
  - jfarmer 13y ago
    It's also not obvious what "average case" means. For example, if we're talking about the asymptotic behavior of the function A(n) = avg { RunningTime(Algo, x) : x is valid input to Algo and len(x) = n } are we assuming that the inputs are drawn uniformly and therefore have equal weight or are we drawing them from a non-uniform distribution? What if some inputs never occur in practice? Worst case and best case are totally unambiguous and don't need any additional clarification. There are just so many knobs one can adjust when defining "average".

baddox 13y ago

Of course. But it's also the worst case. I'm really just wondering if there's a "default" scenario that's being referred to when we just say "f(n) is in O(n)" or does it depend on context?

anonymoushn 13y ago
It depends on context. Generally if people fail to specify, they mean average case, as in "Quicksort takes O(n*lg n) time". There may even be some amortization shenanigans thrown in there, as in "list.append takes O(1) time".
foobarbazqux 13y ago
Quicksort is the exception, in my experience big-O usually refers to worst case running time as opposed to average case or expected running time. CLR(S) [1] sticks to worst case because 1) worst case is a guarantee; 2) the worst case can be frequent; 3) the average case is often roughly as bad as the worst case. This is a widely used textbook, so I generally assume a lot people follow its conventions. [1] https://mitpress.mit.edu/books/introduction-algorithms https://mitpress.mit.edu/books/introduction-algorithms (Introduction to Algorithms)
- jfarmer 13y ago
  It's also not obvious what "average case" means. For example, if we're talking about the asymptotic behavior of the function A(n) = avg { RunningTime(Algo, x) : x is valid input to Algo and len(x) = n } are we assuming that the inputs are drawn uniformly and therefore have equal weight or are we drawing them from a non-uniform distribution? What if some inputs never occur in practice? Worst case and best case are totally unambiguous and don't need any additional clarification. There are just so many knobs one can adjust when defining "average".