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

81–90 of 136 posts

Re: Big-O Algorithm Complexity Cheat Sheet

#81

Post by amalcon »

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

If one takes the time to select optimal pivots it becomes O(nlogn). The selection is free from a big-O perspective, because it's O(n) immediately before the O(n) list division step.

Of course, nobody does this, because the selection is not really free. The constant factor cost of choosing the optimal pivot hurts the average case, making the modified quicksort tend to do worse than heapsort or introsort.

Re: Big-O Algorithm Complexity Cheat Sheet

#83

Post by gizmo686 »

sltkr wrote: post #74
vault_ wrote: post #61

Earlier quoted context omitted.

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

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.

Re: Big-O Algorithm Complexity Cheat Sheet

#84

Post by Goladus »

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

If you understand a concept, then you can reason its big O. Memorization implies a superficial understanding that may be revealed later.

Interestingly enough this works both ways. To say more accurately, memorization MAY imply superficial understanding. Memorization (and associated intuitive pattern-matching) may also lead to understanding.

A cheat sheet like this is also good shortcut refreshing one's memory of the concepts if this knowledge is not used on a regular basis.

Re: Big-O Algorithm Complexity Cheat Sheet

#85

Post by jiggy2011 »

Goladus wrote: post #84
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

If you understand a concept, then you can reason its big O. Memorization implies a superficial understanding that may be revealed later. Interestingly enough this works both ways. To say more accurately, memorization MAY imply superficial understanding. Memorization (and associated intuitive pattern-matching) may also lead to understanding. A cheat sheet like this is also good shortcut refreshing one's memory of the…

I agree, our brains are good at recognizing patterns. So some amount of rote memorization of data can help us see these patterns.

I remember learning the 9 * table as a child and suddenly realizing that n * 9 = (n * 10) - n , thinking "hmm, does n * x = n * (x + 1) - n" why yes it does!

Re: Big-O Algorithm Complexity Cheat Sheet

#86

Post by saraid216 »

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

Maybe they wanted both answers?

Re: Big-O Algorithm Complexity Cheat Sheet

#87

Post by tlarkworthy »

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

Re: Big-O Algorithm Complexity Cheat Sheet

#88

Post by crossroads091 »

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

What was the second answer?

Re: Big-O Algorithm Complexity Cheat Sheet

#89

Post by mindcrime »

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…

Why 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. :-(

Re: Big-O Algorithm Complexity Cheat Sheet

#90

Post by calebegg »

Why 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".

Post reply on HN