Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Big-O Algorithm Complexity Cheat Sheet

bigocheatsheet.com

Post reply on HN
Print view View original

61–70 of 136 posts

Re: Big-O Algorithm Complexity Cheat Sheet

#61

Post by vault_ »

pbiggar wrote: post #47
vault_ wrote: post #9

This 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.

Is it nonlinear even if you have a maximum number of digits in the numbers you're sorting (like say, 64-bit integers)?

Re: Big-O Algorithm Complexity Cheat Sheet

#62

Post by glass_of_water »

mixedbit wrote: post #27
wting wrote: post #4

You 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…

Yeah BFS/DFS are O(n) for graphs and trees.

Re: Big-O Algorithm Complexity Cheat Sheet

#63

Post by pbiggar »

nostrademons wrote: post #59
pbiggar wrote: post #47

Earlier 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.

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 :)

Re: Big-O Algorithm Complexity Cheat Sheet

#64

Post by pbiggar »

sbov wrote: post #60
pbiggar wrote: post #49

Earlier quoted context omitted.

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.

All "don't use in production" tags should be accompanied by "unless you really know what you're doing".

Re: Big-O Algorithm Complexity Cheat Sheet

#65

Post by pbiggar »

vault_ wrote: post #61
pbiggar wrote: post #47

Earlier 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)?

See https://news.ycombinator.com/item?id=5655762

Re: Big-O Algorithm Complexity Cheat Sheet

#67

Post by mixedbit »

sillysaurus wrote: post #57
mixedbit wrote: post #54

Earlier quoted context omitted.

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).

Correct :)

Re: Big-O Algorithm Complexity Cheat Sheet

#69

Post by flebron »

vault_ wrote: post #61
pbiggar wrote: post #47

Earlier 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)?

No, if you assume that the size of each object is constant, O notation will swallow it and report that, in terms of the number of items to sort, Radix sort is linear in time.

The usual bound of Omega(n log n), proved using decision trees, is only applicable when your only operation is to compare two elements. Radix sort asks for more than this, and so it can assume a specific structure of its input, so it can violate the lower bound.

Depending on which operations you assume, sorting can become more or less easy. In the extreme case, if you can ask the array "Please sort yourself." as a basic operation, sorting is O(1). Radix sort assumes bitmasking as a basic operation, which falls into the "make things easier" spectrum, leading to an O(n) algorithm under the stated assumption of constant bit length (or any encoding, really, it doesn't really need to be bits).

Re: Big-O Algorithm Complexity Cheat Sheet

#70

Post by flebron »

Retric wrote: post #52

I 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?

Sometimes, people sort things other than the natural numbers below 2^k.
Post reply on HN