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

21–30 of 136 posts

Re: Big-O Algorithm Complexity Cheat Sheet

#21

Post by agf »

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…

They've got the tables on github and I threw up a pull request to fix several color problems w/ the sorting table including this one, and also to add heapsort.

Re: Big-O Algorithm Complexity Cheat Sheet

#22

Post by gizmo686 »

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)

Re: Big-O Algorithm Complexity Cheat Sheet

#23

Post by mitchi »

omershapira wrote: post #16
0xdeadc0de wrote: post #12

Earlier quoted context omitted.

>To download or read the full version of this document you must become a Premium Reader.

WHAT! I'm sorry about that. It's on my own website now: http://playground.omershapira.com/Notes/DS_CS.pdf

This is great! Gratitude

Re: Big-O Algorithm Complexity Cheat Sheet

#24

Post by mitchi »

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

My friend was interviewed by a video game company not long ago and they gave him an algorithmic problem. He asked what the complexity of the algorithm was and the interviewer said O(n). Good hint to have! He passed the interview.

Re: Big-O Algorithm Complexity Cheat Sheet

#25

Post by neilk »

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…

https://github.com/ericdrowell/BigOCheatSheet/blob/master/Ta...

Re: Big-O Algorithm Complexity Cheat Sheet

#27

Post by mixedbit »

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

BFS, DFS are for graphs, not just trees, and their complexity is not b^d (what is b and d anyway?).

Quick sort expected complexity is nlogn and this is different than average complexity. You can also make quicksort worst-case complexity to be nlogn.

You can't sort anything with space smaller than number of items you are sorting.

You can use buble and insertion sort not only for arrays but also for lists and time complexity does not suffer.

Re: Big-O Algorithm Complexity Cheat Sheet

#29

Post by alecbenzer »

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)

Ah, true. I guess the chart should probably distinguish between arbitrary index insertion and appending.

Re: Big-O Algorithm Complexity Cheat Sheet

#30

Post by anoncow »

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

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

Confucius

Post reply on HN