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

41–50 of 136 posts

Re: Big-O Algorithm Complexity Cheat Sheet

#41

Post by dllthomas »

fatemayasmine wrote: post #17
algorias wrote: post #6

This is why it's a terrible idea to ask for some random algorithm runtime in an interview. It says absolutely nothing about programming or reasoning skill. I'd rather ask a candidate to explain their favorite data structure to me and derive it's big-O complexity right then and there. Being able to regurgitate the correct answer doesn't count for anything in my book.

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

Re: Big-O Algorithm Complexity Cheat Sheet

#42

Post by dllthomas »

jiggy2011 wrote: post #38
anonymoushn wrote: post #35

Earlier quoted context omitted.

The math behind this stuff is in the first third of most calculus textbooks. The CS half can be found in CLRS. You can also probably learn it from TopCoder tutorials or usacogate (I recall there being a mirror of usacogate that did not require you to do all of the problems in order to advance).

I'm very bad at calculus , but I can work out Big O intuitively quite easily.

Even average case complexity?

Re: Big-O Algorithm Complexity Cheat Sheet

#43

Post by why-el »

henrikschroder wrote: post #40
anonymoushn wrote: post #35

Earlier quoted context omitted.

The math behind this stuff is in the first third of most calculus textbooks. The CS half can be found in CLRS. You can also probably learn it from TopCoder tutorials or usacogate (I recall there being a mirror of usacogate that did not require you to do all of the problems in order to advance).

CLRS? Why you young whippersnapper! Back in my day it was called CLR, and those three letters were good enough for us! Kids these days... mmanfrin, it's this book: http://en.wikipedia.org/wiki/Introduction_to_Algorithms

The book along was a little terse for me. The videos from OCW however are priceless, even entertaining sometimes.[1]

[1] http://ocw.mit.edu/courses/electrical-engineering-and-comput...

Re: Big-O Algorithm Complexity Cheat Sheet

#44

Post by meepmorp »

jat850 wrote: post #36
mmanfrin wrote: post #31

Question: 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?

Coursera, no doubt. I took 2 courses with Tim Roughgarden; they were awesome. And I just finished 2 more with Sedgewick. If you can find the Sedgewick courses, I recommend picking up his book (actually, I recommend it anyway) - Algorithms, Sedgewick & Wayne, 3rd ed.

Also, there's a book site for the Sedgwick & Wayne book:

http://algs4.cs.princeton.edu/home/

There's a lot of good stuff.

Re: Big-O Algorithm Complexity Cheat Sheet

#45

Post by dllthomas »

gizmo686 wrote: post #22
alecbenzer wrote: post #14

I'm not totally sure what you mean by "dynamic array", but the vector algorithm for insertion (which you should probably at least include, if by "dynamic array" you were implying a more naive insertion scheme) is O(1) amortized.

If we are talking about the same thing (an array that you reallocate to twice its size when you fill), then it has an amortized O(1) time to append something to the end. If you want to insert something in the beggining, you will need to move n elements down an index. A random location will average n/2, which is O(n)

Though with a gap buffer, you can have O(1) to insert/delete at some other point. Costs O(n) to move that point, though.

Re: Big-O Algorithm Complexity Cheat Sheet

#46

Post by derleth »

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…

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

Re: Big-O Algorithm Complexity Cheat Sheet

#47

Post by pbiggar »

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.

Re: Big-O Algorithm Complexity Cheat Sheet

#49

Post by pbiggar »

anonymouz wrote: post #3

I 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".
Post reply on HN