Can 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.
Big-O Algorithm Complexity Cheat Sheet
51–60 of 136 posts
Re: Big-O Algorithm Complexity Cheat Sheet
#52I 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 I mean is the assumption that people would never actually need a useful real world understanding of the topic?
Re: Big-O Algorithm Complexity Cheat Sheet
#53You 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
I hear and I forget. I see and I remember. I do and I understand. Confucius
That's Xunzi, not Confucius. Good quote though.
Re: Big-O Algorithm Complexity Cheat Sheet
#54Earlier quoted context omitted.
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…
> what is a time complexity for finding a next item (according to a key) to a given one in a hash table? Problem ill-stated as posed: Does not specify if the 'next' key is hashed, or even what 'next' means in this context.
Say, the smallest item in a hash table for which item.key is larger than given_item.key. Assume larger-than relation for keys is defined, so for example keys are integeters.
Re: Big-O Algorithm Complexity Cheat Sheet
#55I 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 I mean is the assumption that people would never actually need a useful real world understanding of the topic?
Radix 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.
Re: Big-O Algorithm Complexity Cheat Sheet
#56You 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't sort anything with space smaller than number of items you are sorting.
I assume it's referring to extra space used. Most analysis of space I've seen is referring to this, not the space required to store the elements.
Re: Big-O Algorithm Complexity Cheat Sheet
#57Earlier quoted context omitted.
> what is a time complexity for finding a next item (according to a key) to a given one in a hash table? Problem ill-stated as posed: Does not specify if the 'next' key is hashed, or even what 'next' means in this context.
Say, the smallest item in a hash table for which item.key is larger than given_item.key. Assume larger-than relation for keys is defined, so for example keys are integeters.
Say, the smallest item in a hash table for which item.key is larger than given_item.key.
Well, keys in a hash table are hashed. This implies that unless you're searching for a specific key (e.g. "42") rather than a condition (e.g. "smallest key greater than 42") then the time complexity is necessarily O(N).
Re: Big-O Algorithm Complexity Cheat Sheet
#58You 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…
>what is b and d anyway?
Breadth and depth. These could apply to graphs as well, since these algorithms draw a tree while traversing the graph.
Re: Big-O Algorithm Complexity Cheat Sheet
#59This 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…
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.
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).
Re: Big-O Algorithm Complexity Cheat Sheet
#60I 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 indivi…
When 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".
Except 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.