not once is theta or omega used, so this cheat sheet isn't all that descriptive.
Big-O Algorithm Complexity Cheat Sheet
71–80 of 136 posts
Re: Big-O Algorithm Complexity Cheat Sheet
#72This 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 exoti…
https://github.com/ericdrowell/BigOCheatSheet/blob/master/Ta...
I sent a pull request with heap things, a couple sorts, and interpolation search.
Re: Big-O Algorithm Complexity Cheat Sheet
#73I 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.
For most graph algorithms it doesn't matter in which order you traverse neighbours, you just need to visit them all.
As 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> 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> 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> as a queue, since the priority_queue in 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.
Re: Big-O Algorithm Complexity Cheat Sheet
#74Earlier quoted context omitted.
Radixsort isn't linear ( 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.
Is it nonlinear even if you have a maximum number of digits in the numbers you're sorting (like say, 64-bit integers)?
In that case, most other algorithms (e.g. insertion sort) technically take linear time too (though with a rather impractical constant factor).
Re: Big-O Algorithm Complexity Cheat Sheet
#75not once is theta or omega used, so this cheat sheet isn't all that descriptive.
To 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.
Re: Big-O Algorithm Complexity Cheat Sheet
#76Very 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
Re: Big-O Algorithm Complexity Cheat Sheet
#77You 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
Agree, 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 ta…
> You can also make quicksort worst-case complexity to be nlogn.
Quicksort in the worst take can take O(n^2) time, not O(nlogn).
Re: Big-O Algorithm Complexity Cheat Sheet
#78Question: 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?
Try the video course that goes with the Cormen book on Algorithms. You can start it right now, its not a scheduled course like Coursera but more a repository like Khan.
http://ocw.mit.edu/courses/electrical-engineering-and-comput...
Re: Big-O Algorithm Complexity Cheat Sheet
#79Very 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 re…
You'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.
Re: Big-O Algorithm Complexity Cheat Sheet
#80Earlier quoted context omitted.
It'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).
Thank you! So if you put a bound on the size of the keys, let's say 32bit, it becomes linear? Obviously it would be cheating to put a giant number here :)
Right. Basically, if the key size is bounded, then k becomes a constant and it reduces to O(N).