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

1–10 of 136 posts

Re: Big-O Algorithm Complexity Cheat Sheet

#3

Post by anonymouz »

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 individual asymptotic bounds.

Re: Big-O Algorithm Complexity Cheat Sheet

#4

Post by wting »

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

Re: Big-O Algorithm Complexity Cheat Sheet

#6

Post by algorias »

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.

Re: Big-O Algorithm Complexity Cheat Sheet

#9

Post by vault_ »

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 exotic structure like a binomial of fibonacci heap) and there are a lot of tradeoffs in complexity of different operations between them.

Post reply on HN