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

91–100 of 136 posts

Re: Big-O Algorithm Complexity Cheat Sheet

#91

Post by paulolc »

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…

You can contribute and fix the table yourself :). The author welcomes it . https://github.com/ericdrowell/BigOCheatSheet/blob/master/Ta...

Re: Big-O Algorithm Complexity Cheat Sheet

#92

Post by crucialfelix »

Jabbles wrote: post #76

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

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

Re: Big-O Algorithm Complexity Cheat Sheet

#93

Post by bastijn »

crossroads091 wrote: post #88
dllthomas wrote: post #41

Earlier quoted context omitted.

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

What was the second answer?

2 and the "no need for base in big-O" makes 2 :).

Re: Big-O Algorithm Complexity Cheat Sheet

#94

Post by ot »

dllthomas wrote: post #41
fatemayasmine wrote: post #17

Earlier quoted context omitted.

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

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

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

Re: Big-O Algorithm Complexity Cheat Sheet

#95

Post by bastijn »

wfunction wrote: post #68

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

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

Re: Big-O Algorithm Complexity Cheat Sheet

#96

Post by Retric »

nostrademons wrote: post #55
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?

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.

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

Re: Big-O Algorithm Complexity Cheat Sheet

#97

Post by gamegoblin »

rttlesnke wrote: post #77
mixedbit wrote: post #27

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

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

You can use a randomized selection algorithm to find the median in linear time, and if you use the median as a pivot you will never get worst case n^2 behavior.

This is not used in practice because the probability of getting worst case behavior is extremely slim if you do some clever, and cheap, tricks.

Re: Big-O Algorithm Complexity Cheat Sheet

#98

Post by nostrademons »

Retric wrote: post #96
nostrademons wrote: post #55

Earlier quoted context omitted.

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.

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

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

Re: Big-O Algorithm Complexity Cheat Sheet

#99

Post by pbiggar »

gizmo686 wrote: post #83
sltkr wrote: post #74

Earlier quoted context omitted.

In that case, most other algorithms (e.g. insertion sort) technically take linear time too (though with a rather impractical constant factor).

Can you elaborate on that. It is proven that sorting based only on comparisons has a lower bound of nlog(n) comparison operations. Given that algorithms such as insertion sort use only comparison operations to probe the data, I do not see how they can break the bound.

What's nlogn for a known n? A constant - therefore O(1).

Re: Big-O Algorithm Complexity Cheat Sheet

#100

Post by ralph »

msvan wrote: post #53
anoncow wrote: post #30

Earlier quoted context omitted.

I hear and I forget. I see and I remember. I do and I understand. Confucius

That's Xunzi, not Confucius. Good quote though.

http://en.wikiquote.org/wiki/Xun_Zi doesn't seem to have it; perhaps an update's required?
Post reply on HN