Is big-O notation a tool to do best, worst, & aver

Question

Is big-O notation a tool to do best, worst, & average case analysis of an algorithm? Or is big-O only for worst case analysis, since it is an upper bounding function?

Answer 1

It is Big O, because orders of magnitude are expressed like O(n), O(logN), etc.

The best, worst, and average cases of an algorithm can all be expressed with Big O notation.

For an example of this applied to sorting algorithms, see

http://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_of_algorithms

Note that an algorithm can be classified according to multiple, independent criteria such as memory use or CPU use. Often, there is a tradeoff between two or more criteria (e.g. an algorithm that uses little CPU may use quite a bit of memory).

Answer 2

Big "O" is a measure of asymptotic complexity, which is to say, roughly how an algorithm scales as N gets really large.

If best & worse converge to the same asymptotic complexity, you can use a single value - or you can figure them out seperately (for example, some sorting algorithms have completely different characteristics on sorted or almost-sorted data than on un-sorted data).

The notation itself doesn't convey this though, how you use it does.

---

... Or is big-O only for worst case analysis ...

If you give just one asymptotic complexity for an algorithm, it doesn't tell the reader whether (or how) the best and worst case differ from the average.

If you give best-case and worst-case complexity, it tells the reader how they differ.

By default, if a single value is listed, it is probably the average complexity which may (or may not) converge with the worst-case.