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

101–110 of 136 posts

Re: Big-O Algorithm Complexity Cheat Sheet

#101

Post by wfunction »

bastijn wrote: post #95
wfunction wrote: post #68

If you need this, you're doing yourself a disservice by looking at it. Go back and learn the concepts so that you're not memorizing anything.

What if you do not use this for an interview, butalready have a job that doesnt require you to apply this every day? I know a lot of these algorithms, but not all. I hardly ever need them, but when I do this might be a good starter to browse from. thinking cheat sheets are only for interviews is limited. I would say knowing everything from head is useless with todays internet. Have a solid base, understand a few and…

> thinking cheat sheets are only for interviews is limited

I never even used the word "interview", are you sure you're responding to the correct comment?

Re: Big-O Algorithm Complexity Cheat Sheet

#102

Post by jules »

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

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.

Re: Big-O Algorithm Complexity Cheat Sheet

#103

Post by sltkr »

gizmo686 wrote: post #83
sltkr wrote: post #74

Earlier quoted context omitted.

In that case, most other algorithms (e.g. insertion sort) technically take linear time too (though with a rather impractical constant factor).

Can you elaborate on that. It is proven that sorting based only on comparisons has a lower bound of nlog(n) comparison operations. Given that algorithms such as insertion sort use only comparison operations to probe the data, I do not see how they can break the bound.

The O(n log n) bound is a worst-case upper bound, which is a tight bound if all elements are distinct. It doesn't apply if there are guaranteed to be a sufficient number of duplicates.

For example, one might implement a variant of InsertionSort that stores a duplicate count for distinct elements, and then an insertion sort on e.g. 32-bit integers would require at most 4294967296 comparisons per insertion -- a constant factor that can be technically ignored in the complexity analysis. (I did warn you that the constant factor would become unwieldy!)

Note that this doesn't require values to be integers -- it suffices for them to be comparable with a lot of duplicates. The variant of InsertionSort described above would require O(k×n) comparisons where `n` is length of the input list and `k` is the number of distinct values, or O(n) whenever `k` is bounded by a constant (as required for radixsort to work in linear time).

That's not to say that radixsort doesn't outperform other sorting algorithms in practice -- it usually does. However, that isn't obvious from a strictly complexity theoretic point of view.

Re: Big-O Algorithm Complexity Cheat Sheet

#104

Post by blt »

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.

Favorite data structure, that's a funny idea. Like asking a candidate to explain their favorite size of wrench.

Re: Big-O Algorithm Complexity Cheat Sheet

#105

Post by ivansavz »

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

As pointed out by msvan, the quote is actually by Xunzi. Here is the original text in Chinese:

不闻不若闻之， 闻之不若见之， 见之不若知之， 知之不若行之； 学至于行之而止矣

I know what you are thinking `Why would you post something in Chinese? How could non-Chinese speakers understand?' and the reason is I want y'all to check out this super cool add of for Firefox: https://addons.mozilla.org/en-us/firefox/addon/perapera-kun-... With this plugin, the meanings of the words show up onmouseover and you can pretty much get the meaning.

Re: Big-O Algorithm Complexity Cheat Sheet

#106

Post by ivansavz »

ralph wrote: post #100
msvan wrote: post #53

Earlier quoted context omitted.

That's Xunzi, not Confucius. Good quote though.

http://en.wikiquote.org/wiki/Xun_Zi doesn't seem to have it; perhaps an update's required?

Check out: http://www.barrypopik.com/index.php/new_york_city/entry/tell... it has a bunch of translations and transliterations of this quote.

Re: Big-O Algorithm Complexity Cheat Sheet

#107

Post by ufo »

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 depends a lot on your input and the problem you want to solve. If we talk about the Simplex algorithm that most people use, empirically it takes around cubic time but its still an open problem to find a base-choide heuristic that does not have pathological exponential worst case performance. 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.

Finally, you got me when it comes to the numerical stuff (eigenvectors and matrix inversion). I haven't looked into that in a while.

Re: Big-O Algorithm Complexity Cheat Sheet

#108

Post by ufo »

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 than using adgacency lists (or vectors) is simpler and does the job just as well.

Re: Big-O Algorithm Complexity Cheat Sheet

#109

Post by nostrademons »

jules wrote: post #102
nostrademons wrote: post #59

Earlier quoted context omitted.

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

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.

Re: Big-O Algorithm Complexity Cheat Sheet

#110

Post by Retric »

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…

True enough. The idea for Big-O notation is really cost = O(whatever) * (algorithms constant difficulty factor) + (algorithms overhead). My point is if you start adding difficulty factors then the same terms often wind up in your other algorithms. Granted string comparisons are generally O(log k) and pure Radix would end up as O(k) but you can also short circuit a MSD Radix sort if the buckets are small enough which effectively drops things back to O(log k) assuming sparse inputs. (if it's not sparse your not going to be doing anything past a depth of about 4 anyway.)
Post reply on HN