19 ms·
Big-O Algorithm Complexity Cheat Sheet
- exabrial 13y ago/trolling on Awesome. Next time I'm trying to pass some silicon valley interview, I'll have to look this up. Till then, I think I have more practical problems to worry about. /trolling off
- anonymouz 13y agoI suppose the general idea for the colors is something like: green = best in category, red = worst in category, yellow = neither best nor worst? In that case bubble sort and insertion sort should be green for the best-case time complexity ( O(n) vs. O(n log(n)) for quicksort/mergesort). It might also be interesting to make the plot dynamic and allow the visitor to play with different implicit constants for the individual asymptotic bounds.
- agf 13y agoThey've got the tables on github and I threw up a pull request to fix several color problems w/ the sorting table including this one, and also to add heapsort.
- pbiggar 13y agoWhen reading it, I felt that red was "don't use in production", green was "fine to use in production" and yellow was "maybe use in production".
- sbov 13y agoExcept insertion sort is faster than quicksort for smaller N because of the overhead involved in quicksort - quicksort has large constants which big-O notation isn't designed to show. This is why many library sorting algorithms fall back to insertion once the things you are sorting gets small enough.
- pbiggar 13y agoAll "don't use in production" tags should be accompanied by "unless you really know what you're doing".
- Zarel 13y agoIt seems to be just: O(1) green O(log n) green O(n) red O(n log n) yellow O(n^2) red Which is weird, since green-green-red-yellow-red is a really confusing order. I don't know why they did it that way.
- wting 13y agoYou can pass some interviews by blindly memorizing, but it's unnecessary. If you understand a concept, then you can reason its big O. Memorization implies a superficial understanding that may be revealed later. If you don't understand something, spend a few hours and implement it. "I hear and I forget. I see and I remember. I do and I understand." - Confucious
- nutjob123 13y agoThis was my immediate reaction. It is very easy and common for an interviewer to make a subtle change to how a common data structure or algorithm would work and then ask for complexity. Ex: Changing the quicksort pivot selection method.
- mitchi 13y agoMy friend was interviewed by a video game company not long ago and they gave him an algorithmic problem. He asked what the complexity of the algorithm was and the interviewer said O(n). Good hint to have! He passed the interview.
- mixedbit 13y agoAgree, buy a good book (for example Cormen), learn the algorithms and implement them to get a good understanding. Try to use the table to answer a following question: what is a time complexity for finding a next item (according to a key) to a given one in a hash table? Memorizing such stuff does not make much sense, but if you understand basic concepts, you will figure it out quickly. There are basic errors in the table: BFS, DFS are for graphs, not just trees, and their complexity is not b^d (what is b and d anyway?). Quick sort expected complexity is nlogn and this is different than average complexity. You can also make quicksort worst-case complexity to be nlogn. You can't sort anything with space smaller than number of items you are sorting. You can use buble and insertion sort not only for arrays but also for lists and time complexity does not suffer.
- paulolc 13y agoYou can contribute and fix the table yourself :). The author welcomes it . https://github.com/ericdrowell/BigOCheatSheet/blob/master/Tables.html https://github.com/ericdrowell/BigOCheatSheet/blob/master/Ta...
- andreasvc 13y agohttp://webcache.googleusercontent.com/search?q=cache:PPvTs45TpbEJ:bigocheatsheet.com/ http://webcache.googleusercontent.com/search?q=cache:PPvTs45...
- algorias 13y agoThis is why it's a terrible idea to ask for some random algorithm runtime in an interview. It says absolutely nothing about programming or reasoning skill. I'd rather ask a candidate to explain their favorite data structure to me and derive it's big-O complexity right then and there. Being able to regurgitate the correct answer doesn't count for anything in my book.
- fatemayasmine 13y agoOften the followup question to what is the O notation of X is why? So if you are just going to memorize the cheat sheet then it won't get you very far. It is good to know what you should know about though.
- dllthomas 13y agoI was asked the O() of binary search. I said "log n". They asked "what base?" ... obviously they wanted 2, but O() doesn't work that way - changing base is a constant factor. Sometimes there's a tension between figuring out someone's understanding of the algorithm and someone's understanding of the notation (and math behind it). Of course, I gave them both answers...
- ot 13y ago> changing base is a constant factor. Only if the base is constant. For example B-trees have O(log_B n)-time operations, and you can't ignore the B because it is a parameter (hence non-constant).
- saraid216 13y agoMaybe they wanted both answers?
- crossroads091 13y agoWhat was the second answer?
- 13y ago
- omershapira 13y agoSlightly academic, but this cheat sheet gives out some shorthand explanations to many of the methods in the Big-O document: http://www.scribd.com/doc/39557873/Data-Structures-Cheat-Sheet http://www.scribd.com/doc/39557873/Data-Structures-Cheat-She...
- 0xdeadc0de 13y ago>To download or read the full version of this document you must become a Premium Reader.
- omershapira 13y agoWHAT! I'm sorry about that. It's on my own website now: http://playground.omershapira.com/Notes/DS_CS.pdf http://playground.omershapira.com/Notes/DS_CS.pdf
- mitchi 13y agoThis is great! Gratitude
- AYBABTME 13y agoThis is very shallow and of limited use.
- kintamanimatt 13y agoIt's a cheatsheet, not a tutorial.
- rhizome 13y ago"The map is not the territory."
- vault_ 13y agoThis is a pretty limited list of algorithms. It should definitely include linear time sorting algorithms (e.g. bucket or radix sort), as well as graph algorithms (shortest path at least, but also probably all pair shortest path and minimum spanning tree). There should also be a section about heaps and their operations. There are a huge number of ways to implement a heap (e.g. linked list, binary tree, or a more exotic structure like a binomial of fibonacci heap) and there are a lot of tradeoffs in complexity of different operations between them.
- omershapira 13y agoThis sounds like a Wikipedia Subportal. If you want help building it, let me know.
- neilk 13y agohttps://github.com/ericdrowell/BigOCheatSheet/blob/master/Tables.html https://github.com/ericdrowell/BigOCheatSheet/blob/master/Ta...
- vault_ 13y agoI sent a pull request with heap things, a couple sorts, and interpolation search.
- pbiggar 13y agoRadixsort isn't linear (https://en.wikipedia.org/wiki/Radix_sort https://en.wikipedia.org/wiki/Radix_sort). I have actually published research that said Radixsort was linear, only to have it later explained to me that it is not linear, for a subtle an hard to remember reason involving number theory.
- nostrademons 13y agoIt's O(k * n) where k is the number of digits. It takes log-b(N) digits to represent N distinct integers in base-b, so O(k * N) reduces to O(N log N) when there's no bound on the range of keys. It's still pretty useful for sorting data where you know the keys are small integers (say, less than a machine word).
- lettergram 13y agoActually walking through each problem is the only way to understand. There's not even a point in memorizing, it takes longer to memorize than to actually learn how to come up with those values.
- alecbenzer 13y agoI'm not totally sure what you mean by "dynamic array", but the vector algorithm for insertion (which you should probably at least include, if by "dynamic array" you were implying a more naive insertion scheme) is O(1) amortized.
- gizmo686 13y agoIf we are talking about the same thing (an array that you reallocate to twice its size when you fill), then it has an amortized O(1) time to append something to the end. If you want to insert something in the beggining, you will need to move n elements down an index. A random location will average n/2, which is O(n)
- alecbenzer 13y agoAh, true. I guess the chart should probably distinguish between arbitrary index insertion and appending.
- dllthomas 13y agoThough with a gap buffer, you can have O(1) to insert/delete at some other point. Costs O(n) to move that point, though.
- fmax30 13y agoI don't know why people don't use balanced BST ( std::map in c++) for storing the adjacency lists of a graph. Sure the insertion would take O(log n) time but , I think the overall benefit would be greater than the costs. Correct me if I am wrong.
- deleted 13y ago[deleted]
- mixedbit 13y agoFor most graph algorithms it doesn't matter in which order you traverse neighbours, you just need to visit them all.
- flebron 13y agoAs an aside, trees (Red-Black trees for std::map in libstdc++) have terrible locality, and thus cache behavior. In general, for reasonable n, it's even going to be better to have a vector<vector<int>> in which you literally push to each vector (for amortized O(1) each time) when you find an adjacency. In the case of dense graphs, yes, adjacency matrices will be even better, since you're going to pay the size cost anyway, and you may as well do it up front and not pay the resizing charges. From my experience, using vector<list<int>> behaves more poorly due to terrible locality of lists. My use of red-black trees for graphs is mostly limited to implementing Dijkstra using set<pair<cost, node_index>> as a queue, since the priority_queue in <queue> does not have a DecreaseKey operation. Using that set (and some map (needn't be std::map, could well be a vector) of node_index to cost for faster compare during Dijkstra's neighbor loop) can make for a very fast, short, and easy to implement Dijkstra. My usage is mostly competitive programming, so YMMV.
- gsg 13y agoTrees don't have to have terrible locality. There are a number of tricks to encode parts of the tree structure into nice flat blocks. (This can involve some memory overhead, which may or may not be offset by the space saved on pointers depending on the size of elements.) Just because std::set and map are completely awful doesn't mean you should completely give up on trees.
- fatemayasmine 13y agoIt is smart how you can edit the table and contribute via Github.
- montecarl 13y agoI would like to see the same type of complexity cheat sheet for algorithms for common math problems: addition, multiplication, division, subtraction, factorization, solving linear systems, solving eigen systems, matrix inversion, etc.
- ufo 13y agoThose depend a lot on the context. Firstly, the complexity for the arithmetic operations you listed mostly only matters if you are working with big numbers (something that is not very common to be a bottleneck). Factorization doesn't have a polynomial algorithm so I don't see why the complexity matters anyway (its still going to take longer than your lifetime with hard inputs anyway). As for linear systems, it depends a lot on your input and the problem you want to solve. If we talk about the Simplex algorithm that most people use, empirically it takes around cubic time but its still an open problem to find a base-choide heuristic that does not have pathological exponential worst case performance. In addition to that, many important problems are modeled as linear programs but will have extra special structure that let them be solved with more efficient algorithms. Finally, you got me when it comes to the numerical stuff (eigenvectors and matrix inversion). I haven't looked into that in a while.
- eru 13y ago> In addition to that, many important problems are modeled as linear programs but will have extra special structure that let them be solved with more efficient algorithms. To specify: Those more efficient algorithms can surprisingly often be expressed as variants of the simplex method, too.
- phene 13y agoOnly worst case is represented by big-O. The others are covered by big and little Omega, little o, and theta notation.
- mmanfrin 13y agoQuestion: I'm a junior software developer that did not get a CS degree. What would be the best way to learn and understand this sort of stuff? Coursera/Khan? A book?
- anonymoushn 13y agoThe math behind this stuff is in the first third of most calculus textbooks. The CS half can be found in CLRS. You can also probably learn it from TopCoder tutorials or usacogate (I recall there being a mirror of usacogate that did not require you to do all of the problems in order to advance).
- jiggy2011 13y agoI'm very bad at calculus , but I can work out Big O intuitively quite easily.
- dllthomas 13y agoEven average case complexity?
- henrikschroder 13y agoCLRS? Why you young whippersnapper! Back in my day it was called CLR, and those three letters were good enough for us! Kids these days... mmanfrin, it's this book: http://en.wikipedia.org/wiki/Introduction_to_Algorithms http://en.wikipedia.org/wiki/Introduction_to_Algorithms
- anonymoushn 13y agoWhy don't your sorted trees support indexing? Mine support indexing in O(lg n) time.
- pbiggar 13y agoCan you annotate it with the subtype of the algorithm. For example, you have O(logN) worst-case space complexity for quicksort - that is not true on all variations, include to naive one.
- Retric 13y agoI never understood why people look at 7-8 sorting methiods and ignore Radix sort which often beats everything else at O(n) average case. https://en.wikipedia.org/wiki/Radix_sort https://en.wikipedia.org/wiki/Radix_sort I mean is the assumption that people would never actually need a useful real world understanding of the topic?
- nostrademons 13y agoRadix sort is technical O(k * n) where k is the number of digits. This is very useful when you know k falls within a bounded range (eg. sorting a bunch of integer keys, all of which range from 0-255), but it reduces to O(n log n) for arbitrary keys, because in general you need log n digits to represent n distinct items.
- Retric 13y agoBy that definition sorting strings using Merge sort for example takes (K * n Log n) which is still worse because string comparison is worst case O(k) not O(1).
- nostrademons 13y agoWhenever you talk big-O you have to be aware of what your primitive operations are. When talking about normal sorting algorithms we usually assume comparison is a primitive operation, and then we're measuring the number of comparisons. This is not actually the case for strings (and several other data types), but that cost is the same regardless of which comparison sort you use, and so it usually doesn't matter in your analysis. With radix sort, you're usually considering using it precisely because K is likely to be significantly smaller than log N, and so it's absolutely relevant to the actual problem at hand. (For that matter, multiplication is not constant time either - it's O(N) in the number of bits, which is O(log N) in the size of the values stored - but this is conveniently forgotten in most algorithm analysis. If you limit the problem to integers that fit into a machine word, then this factor drops out as a constant, and nobody cares.) Regardless of what algorithm you're working with, you have to be aware of the limits of the abstraction you use to analyze it. Fibonacci heaps are O(1), but nobody uses them because the constant factors swamp other simpler algorithms with worse computational complexity. And sometimes it's faster to use a red-black tree (or even linear search over an array) than a hashmap because hashmaps are technically O(k) in key size; red-black trees are too, for comparisons, but in a sparse key space the processor usually only has to examine the first 1-2 characters before it can bail out of the comparison routine while the hashmap has to examine every character.
- Dylan16807 13y agoI'm amused that every single data structure is proportional in size to the amount of data stored and therefore marked as red.
- wfunction 13y agoIf you need this, you're doing yourself a disservice by looking at it. Go back and learn the concepts so that you're not memorizing anything.
- bastijn 13y agoWhat if you do not use this for an interview, butalready have a job that doesnt require you to apply this every day? I know a lot of these algorithms, but not all. I hardly ever need them, but when I do this might be a good starter to browse from. thinking cheat sheets are only for interviews is limited. I would say knowing everything from head is useless with todays internet. Have a solid base, understand a few and google the rest tailored to your situation. I like cheat sheets to quickly remember what to explore.
- wfunction 13y ago> thinking cheat sheets are only for interviews is limited I never even used the word "interview", are you sure you're responding to the correct comment?
- bastijn 13y agotrue, the interview part was for large discussion above. The general concept of my reply applies to your comment though. I think your statement is a bit harsh. Or im misinterpretting what you are trying to say. Saying cheatsheets are useless is not correct imho.
- dmead 13y agonot once is theta or omega used, so this cheat sheet isn't all that descriptive.
- flebron 13y agoTo be fair, people really aren't too interested in Omega, at least not in conjunction with worst cases. Omega is more suitable for best cases, and that in turn is slightly useless without any knowledge of how common it is. For instance, telling you that bubblesort is Omega(n) in the worst case isn't terribly useful, and telling you it's Omega(n) in the best case is somewhat more enlightening (you now have an absolute asymptotic lower bound), but still not really useful without knowing that the best case is going to be very rare (most of your n! possible input permutations have a lot of inversions). Theta is a bit more interesting, however. I think it speaks to the "tameness" of the algorithm.
- Jabbles 13y agoVery few commenters think this is a good idea. The majority of posts lament the rote learning and lack of understanding involved. Why then, is this upvoted so much? Is it that people think the comments are worth reading so much that they upvote the article in the hope that other readers will read the comments? Are the people commenting negatively upvoting the article in the hopes their comments will be more widely read†? Are people afraid of flagging articles? †testable hypothesis, data requested
- crucialfelix 13y agoOr those of that upvoted it aren't the ones that came here to complain about it. There's no reason to assume they are the same parties.
- asafh 13y agoYou're assuming the same set of people that are commenting are those that are upvoting this article. Another hypothesis is that those are two largely disjoint populations on HN. With the smaller one displeased with the article and is likely to express that in comments. The other, larger one is pleased with the article and doesn't bother much with comments.
- mindcrime 13y agoWhy then, is this upvoted so much? First of all... what difference does it make? Beyond that, I's say "it's impossible to know". Upvotes don't have strictly defined semantics on HN. And they also serve as a defacto "bookmark" mechanis. Given both of those factors, it's hard to justify assuming any correlation between "support for the content of the article" and the number of upvotes. Some people are signifying "This headline caught my eye, I want to save it to read later", some are endorsing the content, other don't endorse the content but are voting in favor of the resulting discussion, etc., etc. Is it that people think the comments are worth reading so much that they upvote the article in the hope that other readers will read the comments? Very possibly. Seems like a perfectly reasonable scenario to me. Are people afraid of flagging articles? Why would somebody flag this? It's not off-topic or spam. Just because you think a cheat-sheet isn't a great idea, is hardly a good reason to flag the post. But, then again, flagging also doesn't have particularly well-defined semantics either. :-(
- graup 13y agoWell done! As others pointed out, one might be better off really understanding them, but for a quick overview this is a very usable website.
- tlarkworthy 13y agoIf you want to visualise big O runtime, you draw it on a log-log scale. The linear gradient on the log-log plot is the factor. i.e. if its at 45 degrees its O(n), if its at a gradient of 2:1 its O(n^2). Handy fact to work out your big O without having to do the tedious math! (See http://jcsites.juniata.edu/faculty/kruse/cs2/ch12a.htm http://jcsites.juniata.edu/faculty/kruse/cs2/ch12a.htm)
- eru 13y agoA log-log plot is useful for polynomials, but has nothing to do with big O notation in general.
- tlarkworthy 13y agoI would argue the polynomial factor in an performance computing is about the only thing that matters in a practical setting. The difference between nlog(n) and n, is barely discernible when looking at actual results (and the k factor is much more important then). If your algorithm is x^n or n! your f*ed anyway so its not important cases for tuning. In high performance algoriths, after you add adaptive caching etc. your results are highly dependant on your data, in this casse you expect to get results like O(n^2.34) and stuff so you can't work it out through the analytical approach. Your only recourse is empirical measurement in which case log-log plots are the only sensible choice. The author of the article only has a linear plot on the page which is almost always the worst choice for graphing algorithmic performance, hence I brought up the issue.
- anonymoushn 13y agoIs this correct for n * lg n? The n * lg n on the plot has gradient that is about halfway between n and n^2, but in reality n * lg n ∈ O(n^1.00000000000000000001)
- calebegg 13y agoWhy is O(n) red and O(n log(n)) yellow? Clearly, O(n log(n)) is slower. In general, whether a specific complexity is good or bad differs greatly based on what you're doing. I don't think it's a good idea to have the colors be the same everywhere. A particularly bad instance is how every single data structure is O(n), which is red/"bad".
- deleted 13y ago[deleted]
- westurner 13y ago* https://en.wikipedia.org/wiki/Computational_complexity_theory https://en.wikipedia.org/wiki/Computational_complexity_theor... * http://mathworld.wolfram.com/ComplexityTheory.html http://mathworld.wolfram.com/ComplexityTheory.html * https://complexityzoo.uwaterloo.ca/Zoo_Glossary#O https://complexityzoo.uwaterloo.ca/Zoo_Glossary#O * http://dbpedia.org/resource/Depth-first_search http://dbpedia.org/resource/Depth-first_search * http://en.wikipedia.org/wiki/Category:Infobox_templates http://en.wikipedia.org/wiki/Category:Infobox_templates * http://www.w3.org/TR/rdf-schema/ http://www.w3.org/TR/rdf-schema/
- oakaz 13y agoIs this only for interviews?
- kriro 13y agoPretty cool, thanks. I think the graph at the end is the most useful thing. Really helps understanding the complexity in relative terms. Adding tree stuff would be cool (especially for search which is often implemented as either a tree or graph version)
- coldcode 13y agoIf you only want to hire me based on answering big-O questions I don't want to work there anyway. 32 years of working on highly complex and performant stuff and not once did I think in terms of big-0. Optimizing is not about knowing the math but knowing how to measure and how to interpret what you measure. Big-O might make you feel smart but it's a tiny part of actually constructing something complex and optimal.
- rdtsc 13y agoI mostly agree. big-O knowledge helps you pick the right data structures and algorithms for the job. The idea is that it will often help you avoid having to rediscover all those complexity classes by trial and error when looking at systemtap traces or time stamps in the log stream. For example in real-time systems picking a btree vs a hash based data-structure might work better sometimes since there is a less of a chance of a sudden spike related to hash re-sizing, instead there is a small penalty to be paid during insertion. I believe that. Have I actually measured that? No. Because it would involve re-writing a bunch of code and it would take time. So I don't know if big-O had saved my ass here. That is just one example. Or say when when it comes to large data storage, knowing the base data structure used in the database will give you some expectation as to how it behaves when the size grows. All that said, it is hard to point back in 7+ years and say, aha, I know exactly how many times knowing big-O saved me from spending extra time and effort debugging. I can think maybe only of one or two times recently when I had to think about big-O so I mostly agree with you. It certainly seems that not knowing anything about big-O will not terribly handicap someone who knows how to use debugging and profiling tools. There are probably other more practical bits of knowledge that are more important to know. Despite this these kind of questions are very popular. I see a few reasons. 1) "Big Company" interviews. Big companies love hiring fresh college grads from good schools. Those don't have a lot of relevant software development experience. But they have to be selected and tested somehow so theoretical CS is the goto tool. 2) Other companies just copy the interview questions from big company interviews thinking "well they are so big and successful because they are using these kind of questions to select candidates". Whether it is true or not, I don't know but I believe that processes goes on behind the scenes.
- zukhan 13y agoYou should create an empty version of the cheat sheet so people can test their understanding of various data structures and algorithms.