Is there a master list of the Big-O notation for everything?

Question

Is there a master list of the Big-O notation for everything? Data structures, algorithms, operations performed on each, average-case, worst-case, etc.

Answer 1

Try "Introduction to Algorithms" by Cormen, Leisersen, and Rivest. If its not in there its probably not worth knowing.

Answer 2

Introduction to Algorithms, Second Edition, aka CLRS (Cormen, Leiserson, Rivest, Stein), is the closest thing I can think of.

If that fails, then try The Art of Computer Programming, by Knuth. If it's not in those, you probably need to do some real research.

Answer 3

The Cormen book is more about teaching you how to prove what Big-O would be for a given algorithm, rather than rote memorization of algorithm to its Big-O performance. The former is far more valuable than the latter, and requires an investment on your part.

Answer 4

In c++ the STL standards is defined by the Big-O characteristics of the algorithms as well as the space requirements. That way you could switch between competing implementations of STL and still know that your program had the same-ish runtime characteristics. Particularily good STL implementations could even special case lists of particular types to be better than the standard-requirements.

It made it easy to pick the correct iterator or list type for a particular problem, because you could easily weigh between space consumption and speed.

Ofcourse Big-O is only a guide line as all constants are removed. If an algorithm runs in k*O(n), it would be classified as O(n), but if k is sufficiently high it could be worse than O(n^2) for some values of n and m.

Answer 5

Dictionary of Algorithms and Data Structures is a fairly comprehensive list, and includes complexity (Big-O) in the algorithms' descriptions. If you need more information, it'll be in one of the linked references, and there's always Wikipedia as a fallback.