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

111–120 of 136 posts

Re: Big-O Algorithm Complexity Cheat Sheet

#111

Post by geophile »

pbiggar wrote: post #47
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.

It all depends on what you're counting. Sort algorithm analysis typically counts key comparisons or record movement. In radixsort (and trie algorithms in general), you are relying on operations on digits of the key, not comparisons of entire keys. So linear isn't necessarily wrong, but you do have to say what you're counting.

Number theory? Not seeing the connection.

Re: Big-O Algorithm Complexity Cheat Sheet

#112

Post by pbiggar »

geophile wrote: post #111
pbiggar wrote: post #47

Earlier quoted context omitted.

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.

It all depends on what you're counting. Sort algorithm analysis typically counts key comparisons or record movement. In radixsort (and trie algorithms in general), you are relying on operations on digits of the key, not comparisons of entire keys. So linear isn't necessarily wrong, but you do have to say what you're counting. Number theory? Not seeing the connection.

It wasn't number theory, but I couldn't remember and was hand-waving.

Re: Big-O Algorithm Complexity Cheat Sheet

#114

Post by Zarel »

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…

It seems to be just:

O(1) green O(log n) green O(n) red O(n log n) yellow O(n^2) red

Which is weird, since green-green-red-yellow-red is a really confusing order. I don't know why they did it that way.

Re: Big-O Algorithm Complexity Cheat Sheet

#115

Post by popol »

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…

> BFS, DFS are for graphs, not just trees BFS and DFS are applied to graphs, but the search space is indeed a tree.

Re: Big-O Algorithm Complexity Cheat Sheet

#116

Post by fmax30 »

ufo wrote: post #108
fmax30 wrote: post #15

I don't know why people don't use balanced BST ( std::map in c++) for storing the adjacency lists of a graph. Sure the insertion would take O(log n) time but , I think the overall benefit would be greater than the costs. Correct me if I am wrong.

Storing the graph structure in a BST is only useful if your graph is very sparse and you need to have fast lookup for checking specific edges (say, given two nodes, find the cost for the edge between them). If your graph is dense, using a an adjacency matrix is simpler and will be faster most of the time. If you don't need to query specifific edges and all you need to do is iterate over the edges for given vertices t…

if my graph is dense then would using a adjacency matrix take like O(V^2) space complexity ? Anyway I was just suggesting this because I use it in practice. Just wanted to know the cons of it if any.

Re: Big-O Algorithm Complexity Cheat Sheet

#117

Post by eru »

nostrademons wrote: post #98
Retric wrote: post #96

Earlier quoted context omitted.

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

> For that matter, multiplication is not constant time either - it's O(N) in the number of bits [...]

Actually, multiplication is worth than O(bits). A naive approach will yield O(bits^2), but you can get something like O(bits^r) where r is not too much bigger than 1. See https://en.wikipedia.org/wiki/Multiplication_algorithm#Fast_... for an introduction

Re: Big-O Algorithm Complexity Cheat Sheet

#118

Post by eru »

tlarkworthy wrote: post #87

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 )

A log-log plot is useful for polynomials, but has nothing to do with big O notation in general.

Re: Big-O Algorithm Complexity Cheat Sheet

#119

Post by eru »

jiggy2011 wrote: post #48
dllthomas wrote: post #42

Earlier quoted context omitted.

Even average case complexity?

Enough to guess with a fairly high degree of accuracy.

Only for the simple stuff (and that might be good enough for you). Average case complexity is devilishly hard in general, and even worst case complexity is super hard. E.g. try analysing fibonacci heaps `intuitively'.

Re: Big-O Algorithm Complexity Cheat Sheet

#120

Post by eru »

ufo wrote: post #107
montecarl wrote: post #26

I would like to see the same type of complexity cheat sheet for algorithms for common math problems: addition, multiplication, division, subtraction, factorization, solving linear systems, solving eigen systems, matrix inversion, etc.

Those depend a lot on the context. Firstly, the complexity for the arithmetic operations you listed mostly only matters if you are working with big numbers (something that is not very common to be a bottleneck). Factorization doesn't have a polynomial algorithm so I don't see why the complexity matters anyway (its still going to take longer than your lifetime with hard inputs anyway). As for linear systems, it depend…

> In addition to that, many important problems are modeled as linear programs but will have extra special structure that let them be solved with more efficient algorithms.

To specify: Those more efficient algorithms can surprisingly often be expressed as variants of the simplex method, too.

Post reply on HN