In this issue, it was decided that quicksort worst case runtime is O(n^2) based on a paper which contained an assumption that leads to unnecessarily slow quicksort implementations. In my opinion, the cheat sheet should contain the running time of the asymptotically fastest implementation of each algorithm, which runs in O(n log n) in this case.

• In set terms Theta() is the intersection of O() and Omega() [more info at the highest ranked answer in this complexity question on stackoverflow].
• Very few algorithms have Theta() (merge sort being one of the few examples), however all algorithms in the cheatsheet seem to have entries).
• There also seems to be mixing between best, average, worst and the mathematical concepts of big Omega, Theta, O.

I think it's misleading to say that it's O(1), since it assumes that you already have the element previous to the one to delete. It should also specify that there is a search time involved, either by specifying O(n) or as a tooltip. Also, in the wiki source, it is specified that there is a search time.

Right now, the worst-case space complexity for Quicksort, is set to O(log(n)). This is not right - the average-case space complexity is Θ(log(n)), but when you attempt to sort an already sorted list, this will lead into n recursive calls on the stack, thus the O(n) worst-case space complexity.

Since this is a cheatsheet I'd say it would be nice to also have it in a PDF form for offline/print use.

What do you think?

@ericdrowell committed 1193ed2 13 months ago.

The changes in that commit are wrong. Theta and Omega do not mean average case and best case time complexity. Theta, Omega, and Big-O are completely orthogonal to the concepts of average-case, best-case, and worst-case. Strictly speaking, most of the time we say an algorithm is O(p) for some polynomial p, we really mean it is Θ(p). In any case, the information on this page is misleading, and my students now come into class believing that theta is equivalent to "average case," when this is plainly false, because they have heard that this page is the premier resource for algorithm time complexity.

Suggest reverting 1193ed2.

There is variety of ways to represent graphs, and complexity of graph operations depends on graph representation. However, I am curious how you estimated complexity of edge insertion, which is the same for all graph representations (add Edge, O(1)). What kind of graph implementation you assume hereby? Do you assume that you have a hash_map for vertices in adjacency list, which makes it O(1)? If so, it would be good to update the information.

To depict the issue, one can imagine very simple representation of a graph with vertices that contain strings. In c++ we can represent adjacency list using STL collections, such as:
std::mapstd::string,std::setstd::string adjacency_list;
Now, method to add edge, i.e. addEdge("baby","carrot"), first has to look up for position of the vertex ("baby") in the adjacency list, which is O(logn) in this case.

Currently, the nav bar has
Searching
Sorting
Graph
Comments

It's missing Data Structures and there's a bit of name collision between graph algorithms and the Big-O complexity graph.

One suggestion is to use GitHub pages and just add a CNAME to your repository. If you create a branch called gh-pages, it will automatically update the website. This way you won't have to worry about keeping the server and code in sync.

Read more about GitHub Pages here.

Could we update the recommended reading section to point to the 6th edition of cracking? Currently it points to the 5th edition

Link:
http://www.amazon.com/Cracking-Coding-Interview-6th-Programming/dp/0984782850/ref=sr_1_1

Shouldn't the worst case insertion/deletion time of a Singly-Linked List be O(n). Both would involve traversal of the entire linked list to find the last node.

The redbubble product link leads to "product not found" page.

There are log2(n) levels of recursion and at each level n elements are used. that makes the total O(n log n) in space complexity.

Big-O notation can be helpful for lots of things, but amortized runtimes can be just as helpful as big-O time-complexities (sometimes moreso).

Including them in the tables would be incredible.

Would be nice to have :)

http://en.wikipedia.org/wiki/Big_O_notation#Related_asymptotic_notations

@ericdrowell
I made a contribution via this PR: #81

Please add me if you don't mine to the list of contributors.

BigOCheatSheet is a great idea, and glad to be a small part of it.

Cartresian -> Cartesian

Please add square root of x to the complexity /growth image

Coloring is hard to define.

For eg, finding the shortest-path in a graph with negative edges:

• Dijkstra is fast, takes O((V+E) log V) but does work with negative edges.
• Bellman-Ford is O(VE), it's way slower than Dijkstra.

Would you put Bellman-Ford in green because it's the fastest you can do in that situation? Or in red because it's slower than Dijkstra?

How about absolute colors for each of the following categories?

• white: constant-time, O(1)
• blue: sub-linear, like O(log n) or O(sqrt n)
• green: linear, O(n)
• yellow: quasilinear, like O(n log n)
• red: higher, like O(n^2), O(n^2 log n), O(n^3)

I don't think you would ever want to list an exponential time algorithm, O(2^n), O(n!), O(n^n), so no color needed

If you think about orders of magnitude of difference, I think the buckets ("Horrible", "Bad", "Fair", "Good", "Excellent") are done incorrectly.

O(2^n) and O(n^2) are vastly different, but both are labeled "Horrible." O(2^n) algorithms fall over long before n = 1000, O(n^2) algorithms can be practical and useful for n = 1 million.

O(n log(n)) and O(n) are not very different, but one is "Good" and the other "Fair". Both are practical for roughly the same class of problem. In many cases O(n log(n)) algorithms are preferred in practice over O(n) algorithms for non-complexity reasons, because the theoretical complexity difference is dominated by other factors.

O(log(n)) and O(1) are actually quite different, but both are labeled "Excellent." This is the least worrying of these, but if any factor of log(n) is important enough to distinguish labels, it's the first one. In this case, it's mostly because of CPU caches and memory accesses. Small constant memory access is relatively cheap, O(log(n)) memory accesses can have dramatic effects on cache misses and resulting performance of a whole program.

big o

o and theta

omega

big theta

I thought that the data structures section should have a more general link to an associative array/map/dictionary. I see a link exists for a hash table which is just an implementation of an associative array.

The time complexities for Shell Sort on bigocheatsheet.com are now nothing like the ones listed on the wikipedia page:
https://en.wikipedia.org/wiki/Shellsort

Incidentally, bigoref.com seems to have this mostly right, but not completely:
josem/bigoref#3

B+ Tree

I already provide a PR here #153
Might as well review it immediately
Thank you 🙏 @ericdrowell

Comparing bucketsort to quicksort is like comparing apples and oranges. It is also important to understand that O(n log n) for comparison sorting is asymptotically optimal (up to a constant factor), and so it should not be ``Bad''.

Hi!

Would you mind adding all the code of the page? I'd like to try to integrate MathJax.

http://en.wikipedia.org/wiki/Binary_search_algorithm

Probably the only thing else it needs.

There are cases where a fixed-size array is a good data structure. It has always O(1) for insertion, deletion and search Why is it not there yet?! :-)

I recommend the website add an Open Graph meta tag so that an image preview is added to link as it's shared.

Timsort space complexity is indicated as O(1) in yellow on the poser, but must be O(n).

Kruskal, Dijktra, Prim, Hungarian and so on...

Can we replace the existing image with the one below?
Shell sort has time complexity O((nlogn)^2) in its average and worst case, but this function is not included in the chart provided.

Here's an iframe linked to an interactive version:

<iframe width="840" height="466" seamless frameborder="0" scrolling="no" src="https://docs.google.com/spreadsheets/d/1V6hJ9R0Tx9JMa0pEUq2TTkMFCkVO00vdusFFUYLmhbw/pubchart?oid=1753507166&amp;format=interactive"></iframe>

@caspar

In some of these tables (e.g. array sorting), a 'best' and 'average' case are included along with the worst case, and they use the big O notation as well. Are the best case runtimes of these algorithms not Omega and Theta, respectively?

I'm in the process of beefing up my CS theory and there seems to be a ton of conflicting information in the community about asymptotic analysis and Big O notation. Not trying to nitpick on this (and my understanding of this could be off-base), but wouldn't the best case runtime for an algorithm be represented as Ω(n) and the average as ϴ(n), not O(n) since Big O implies the worst case?

In the sorting table, it would be relatively easy (and helpful) to indicate stabilities. If so I'd submit an initial pull request.

You seem to be making the common mistake of thinking big-Theta means average case and big-O means worst case, which is not correct.

Either big-O or big-Theta or big-Omega can be used meaningfully to describe any of best, average, or worst case -- the concepts are completely orthogonal.

To be mathematically accurate your page should have Theta everywhere.

Last year, I forked and translated the entire html to brazilian portuguese, even the articles url. It would be very interesting if the official website had an option to choose the language, so that other contributors could translate to their mother languages and reach more people.

Brazilian translation

Hey, I just wanted to check if this project is still being maintained? It seems like the site is used pretty heavily as a reference and thankfully a lot of these algorithms don't change over time (hehe...) in runtime complexity so more or less it's been great. The last commit in this repo has been a year ago so I'm hoping it isn't going to die off. At the very least, maybe there can be a handful of the contributors that would be willing to help maintain this site and they can be distinguished?

It also looks like a giant portion of runtimes was deleted by accident..? Not that I'm involved but I'm seeing a lot of redundant PRs adding the same run times so it would be good if these were either just merged or closed.

Thanks for your hard work on this project @ericdrowell! Let us know :)

Trying to navigate to the site from google results in a server error. The site completely fails to load with bigocheatsheet.com but works if you manually change the url to www.bigocheatsheet.com.

This is sometimes different from the access time.
Example:
https://en.wikipedia.org/wiki/AVL_tree#Traversal

Once a node has been found in an AVL tree, the next or previous node can be accessed in amortized constant time.