CODEWITHSUNDEEP
algorithmdata-structuresbig-o
raldi
raldi

Reputation: 22160

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

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

Upvotes: 17

Views: 4736

Answers (6)

anon
anon

Reputation:

To anyone, who is coming to this question from Google.

http://bigocheatsheet.com/

Upvotes: 0

ephemient
ephemient

Reputation: 204798

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.

Upvotes: 8

Alan
Alan

Reputation: 7064

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.

Upvotes: 6

Soraz
Soraz

Reputation: 6746

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.

Upvotes: 2

Todd Gamblin
Todd Gamblin

Reputation: 59837

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.

Upvotes: 0

Oliver Hallam
Oliver Hallam

Reputation: 4262

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

Upvotes: 2

Related Questions