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

121–130 of 136 posts

Re: Big-O Algorithm Complexity Cheat Sheet

#121

Post by gsg »

fmax30 wrote: post #116
ufo wrote: post #108

Earlier quoted context omitted.

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.

The space taken by an adjacency matrix doesn't depend on edge count. That's why it is usually the favoured representation for dense graphs.

Re: Big-O Algorithm Complexity Cheat Sheet

#122

Post by gsg »

flebron wrote: post #73
mixedbit wrote: post #32

Earlier quoted context omitted.

For most graph algorithms it doesn't matter in which order you traverse neighbours, you just need to visit them all.

As an aside, trees (Red-Black trees for std::map in libstdc++) have terrible locality, and thus cache behavior. In general, for reasonable n, it's even going to be better to have a vector > in which you literally push to each vector (for amortized O(1) each time) when you find an adjacency. In the case of dense graphs, yes, adjacency matrices will be even better, since you're going to pay the size cost anyway, and yo…

Trees don't have to have terrible locality. There are a number of tricks to encode parts of the tree structure into nice flat blocks. (This can involve some memory overhead, which may or may not be offset by the space saved on pointers depending on the size of elements.)

Just because std::set and map are completely awful doesn't mean you should completely give up on trees.

Re: Big-O Algorithm Complexity Cheat Sheet

#123

Post by westurner »

* https://en.wikipedia.org/wiki/Computational_complexity_theor...

* http://mathworld.wolfram.com/ComplexityTheory.html

* https://complexityzoo.uwaterloo.ca/Zoo_Glossary#O

* http://dbpedia.org/resource/Depth-first_search

* http://en.wikipedia.org/wiki/Category:Infobox_templates

* http://www.w3.org/TR/rdf-schema/

Re: Big-O Algorithm Complexity Cheat Sheet

#125

Post by tlarkworthy »

eru wrote: post #118
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.

I would argue the polynomial factor in an performance computing is about the only thing that matters in a practical setting. The difference between nlog(n) and n, is barely discernible when looking at actual results (and the k factor is much more important then). If your algorithm is x^n or n! your f*ed anyway so its not important cases for tuning. In high performance algoriths, after you add adaptive caching etc. your results are highly dependant on your data, in this casse you expect to get results like O(n^2.34) and stuff so you can't work it out through the analytical approach. Your only recourse is empirical measurement in which case log-log plots are the only sensible choice. The author of the article only has a linear plot on the page which is almost always the worst choice for graphing algorithmic performance, hence I brought up the issue.

Re: Big-O Algorithm Complexity Cheat Sheet

#126

Post by kriro »

Pretty cool, thanks.

I think the graph at the end is the most useful thing. Really helps understanding the complexity in relative terms.

Adding tree stuff would be cool (especially for search which is often implemented as either a tree or graph version)

Re: Big-O Algorithm Complexity Cheat Sheet

#127

Post by jules »

nostrademons wrote: post #109
jules wrote: post #102

Earlier quoted context omitted.

Quicksort is O(k*n log n) though since it does O(n log n) comparisons and a comparison is going to be O(k), so radix sort is still asymptotically faster.

See response to Retric: https://news.ycombinator.com/item?id=5656534 A comparison isn't always O(k). It's O(k) for strings. It's O(1) for machine-word integers. It can be much more than O(k) for user-defined types, eg. it can be O(k^3) if you have to multiply a matrix out and take the determinant of the product.

For word sized integers, k=O(1) so radix sort is O(n) and quicksort is O(n log n). If you have a comparison function that takes O(k^3) then you most likely can't even implement a radix sort for it, so the comparison can't be made.

So the fact is that quicksort is a factor O(log n) slower than radix sort. The flip side is that quicksort is more generally applicable to any comparison function whereas radix sort only works for lexicographic sorts. In almost all cases that is exactly what you want, but for example I'm not aware of any way to efficiently sort rational numbers with radix sort.

Re: Big-O Algorithm Complexity Cheat Sheet

#128

Post by kolistivra »

gamegoblin wrote: post #97
rttlesnke wrote: post #77

Earlier quoted context omitted.

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

You can use a randomized selection algorithm to find the median in linear time, and if you use the median as a pivot you will never get worst case n^2 behavior. This is not used in practice because the probability of getting worst case behavior is extremely slim if you do some clever, and cheap, tricks.

Randomized selection algoritm is actually O(N^2) in the worst case. Median of medians is the O(N) worst case selection algorithm.

Re: Big-O Algorithm Complexity Cheat Sheet

#129

Post by ufo »

fmax30 wrote: post #116
ufo wrote: post #108

Earlier quoted context omitted.

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.

Dense graphs, by definition, have close to O(V²) edges already so adjacency matrices aren't wasting space in that case.

Re: Big-O Algorithm Complexity Cheat Sheet

#130

Post by dhruvbird »

nostrademons wrote: post #59
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's O(k * n) where k is the number of digits. It takes log-b(N) digits to represent N distinct integers in base-b, so O(k * N) reduces to O(N log N) when there's no bound on the range of keys. It's still pretty useful for sorting data where you know the keys are small integers (say, less than a machine word).

Actually, it's useful when 'N' (the number of elements) is much larger than 'k', the number of significant digits in the largest number in the set.

If k ∈ Θ(log N), then O(Nk) becomes O(N log N), which is asymptotically no better than any optimal comparison based sort.

However, if k ∈ o(log N), then we get an asymptotically better algorithm.

Post reply on HN