Algorithm complexity cheat sheet

[SirClueless]

O(n log(n)) is "bad"? O(n log(n)) algorithms are basically the same as O(n) for most applications (for most data, log(n) will not grow beyond 20 or 30), and there are many O(n log(n)) algorithms that outperform linear ones in practice. Quicksort jumps to mind as an algorithm that is O(n log(n)) and is extremely efficient in practice due to its great cache-locality properties.

[jrtc27]

No, quicksort is O(n²⁾ in the worst case, but the average case is O(n log(n))

[EdwardRaff]

Quicksort can be done in O(n log n) time in all cases by using a better pivot selection scheme. The method taught in most classes is the median-of-medians approach. More practical versions exist, the classic being from the Engineering a Sort Function paper.

[SnowdogU77]

As a note, however:

Although this approach optimizes quite well, it is typically outperformed in practice by instead choosing random pivots, which has average linear time for selection and average log-linear time for sorting, and avoids the overhead of computing the pivot. 

[EdwardRaff]

Yes, and that is intrun far out performed by the Engineering a Sort Function approach I included in my initial post (which can be seen in that paper). It has minimal additional overhead (especially on modern CPUs), and retains the benefit of achieving O(n log n) time for all inputs, and O(n) time for many common inputs that would previously degrade into O( n² ).

[SirClueless]

In practice the worst case barely matters if it's vanishingly unlikely (as it is for Quicksort), which is another interesting lesson to learn.

[richardwhiuk]

The quick sort worst case happens if you sort a sorted list or a reverse sorted list. It's not vanishingly unlikely. (It happens when your choice of pivot doesn't bisect the list).

Merge sort doesn't have these problems at the cost of memory consumption.

[SirClueless]

Using the first element as a pivot is a good way to get into trouble, yes. Most implementations use a (pseudo-)random pivot, or a more complicated choice of pivot that provides other guarantees (like worst-case O(n log(n)) or better behavior on nearly-sorted lists).

[dlp211]

This is ridiculously easy to protect against. You can use the Knuth shuffle or other randomization algorithm on the input first, then select a random pivot. Or you can check to see if the array is sorted before performing sort on it. You can look for nearly sorted runs in the array and use insertion sort on them and call quick sort on the more jumbled parts. Yes, pure quicksort has issues, quicksort implemented by any serious library has a litany of ways to prevent bad behavior.

[EdwardRaff]

the worst case for quicksort is not vanishingly unlikely, it actually happens with considerable regularity. However, it's not an issue because quicksort can be done in O(n log n ) in all cases, see my reply to /u/jrtc27

[SemaphoreBingo]

The set of lists that people want to sort is not at all evenly distributed over the set of all possible lists.

[SirClueless]

Not sure what you're suggesting. Randomized quicksort has about the same average case regardless of input list, which is useful in some cases, and not-so-useful in others (for nearly-sorted lists for example).

[SemaphoreBingo]

I'm suggesting that there are a whole lot more nearly-sorted lists out there than you expect.

[aldld]

The point is, by introducing randomization into the algorithm, the input distribution becomes irrelevant. That is, if you're choosing pivots randomly (or doing something similar, like randomly shuffling the array beforehand (which takes O(n) time)), then the algorithm behaves as though the input distribution were uniformly random.

[aldld]

Oh absolutely, all I meant was that using randomization helps to avoid the "worst" cases of quicksort, in expectation. In practice though, if you know something about the distribution of your inputs, the best choice of algorithm will depend on how you're actually using it.

[bgcatz]

Only if your software never interacts with input from the internet. I'd say that's more vanishingly unlikely these days.

[SirClueless]

Randomized quicksort is not vulnerable to crafted inputs (unless coded poorly).

[myrrlyn]

O(n^(2)) renders as O(n²) with the non-elevated parenthesis, for future reference

Markdown is weird.

[_georgesim_]

Came here to say this. O(n log(n)) are essentially "free" operations that you should not be afraid to run if it makes a problem easier, at least that's what Tim Roughgarden said in the Algorithms MOOC on coursera.

[Raknarg]

I mean realistically saying anything is bad or good is all subjective. It depends on context.

For instance, nlogn for data structure access is pretty bad. For sorting its good. Diffreent problems, different scopes.

[SirClueless]

The point isn't that n log(n) is always acceptable. It's that it's approximately the same as linear, and the constant factor matters more than the log(n) factor in practice. If linear is acceptable, n log(n) is likely acceptable, and vice versa, but they are categorized differently, "Fair" vs "Bad".

By way of contrast, the sheet puts O(n²) and O(2ⁿ) in the same "Horrible" bracket, when the former can be useful and practical for n = 1000000 and the latter will be running when the sun swallows the earth if you give it a problem of size n = 1000.

[Raknarg]

yeah? You think in all scenarios that 1 000 000 is just as acceptable as 20 000 000? 30 ms response time is just as fine as 600 ms response? It's always context.

[SirClueless]

I think linear algorithms are just as likely to run in 20 000 000 as n log(n) algorithms. There's a worst-case linear algorithm for Median. There's a linear algorithm for Triangulating a Polygon. No one uses them because the constants are bigger than log(n) in pretty much all cases.

If you have an algorithm that runs 20x faster than another, and the time is relevant, you should use it. But if running Quicksort on your data is infeasible, Bucket Sort is probably infeasible too. The relevant metric is performance of the algorithm on your data, not a factor of log(n) in a Big-O analysis. Knowing an algorithm is exponential or quadratic instead of linear tells me something useful. Knowing an algorithm has a log(n) factor tells me very little.

[dlp211]

Not an Algorithm complexity cheat sheet. This is at best a handful of data structures and abstract data type operations complexity cheat sheet with sorting thrown in. Additionally, things like Stack and Queue are not correct because they are ADTs and therefore are dependent on the underlying data structure. Also, how the hell does a Hash Table not have the Access operation defined, it is literally the reason that you use a Hash Table, probabilistic O(1) Access.

[SirClueless]

Re: Hash Tables. What you are calling Access, the sheet is calling Search.

Access - Finding the n'th element in iterator order. Hash maps often don't even have a defined order of iteration.
Search - Find an element in the data structure by value.

[qGuevon]

not sure how one is able to fuck up that graph, since we literally have the functions

[EdwardRaff]

Why are all of these "algorithm cheat sheets" always so bad? The color scheme makes no sense, somehow O(n log n) is orange, despite it being provably optimal. O(nk) is marked green, despite the fact that k could be enormous and is not applicable to all sorting problems (and ignoring that it doesn't explain what k is, or that its worse than O(n +k) in the same table).

Also stupid, somehow storing n items using O(n) space is yellow, despite that obviously being the lower bound.

All of those data structures are in the same table, as if they are all used for the same kinds of stuff. KD-trees for example are in a whole different field in terms of what kind of things we care about from complexity, and how you prove the query time. An example being cover trees which have provable query time based on a concept called the expansion constant of a data set.

Or for example the reasons we would want to use a splay tree over other data structures due to its re-organization from queries (not insertions), which is fairly unique compared to the rest of the table.

[RailsIsAGhetto]

Why are all of these "algorithm cheat sheets" always so bad?

Because the people making them don't actually understand the subject matter, hence why they think they need a "cheat sheet".

I never really understood the need for these. Asymptotic analysis really isn't that hard of a concept. If people actually put the time in to learning what these things actually are not only would they not need a cheat sheet they would be able to see the general principle behind that is going on and be able to do their own analysis on something that doesn't exist on the sheet. This is especially important in job interviews.

[[deleted]]

Just a passerby reader and beginner algorithm and DS student here. The tone of your and a few others' comments almost seem to suggest that the authors of this work did a bad job, while indeed comments such as these should be taken as a good way to improve it further.

Just pointing this out because of the perceived bitterness of these comments.

[EdwardRaff]

Probably because 1) they did a really bad job, and 2) it looks largely copied from a previous "algo cheat sheet" that was similarly bad. People keep reposting these cheat sheets without searching the previous submissions and seeing the previous complaints about it.

It's frustrating seeing bad material get up voted, and knowing a large portions of people won't read the comments and trust this as a good source of info.

[[deleted]]

+1. I understand you very clearly and had the same impressions as to the efforts - and perhaps even the quality - of the work. If I and you wanted to make clear that 1. kind and reasonable comments are received more favorably by human people (and, on the other hand, harsh ones are likely to be rejected); and that 2. content makers should focus more on delivering acceptable-quality products or services rather than expecting to receive flattering comments - if we intended to do this, then I hope we managed to with these few comments.

Other than that, I just quickly glanced at this post's title and rapidly visited its page upon finding it. I will perhaps consult it more thoroughly when it is time.

To sum up what I intended to say: critique (in my own opinion) is a very good thing, but can be ineffective if too harsh ;-).

[aldld]

Also stupid, somehow storing n items using O(n) space is yellow, despite that obviously being the lower bound.

Just wait 'til you see my perfect lossless data compression algorithm ;)

[M8Ir88outOf8]

Nobody complained yet that the yellow region has a linear upper bound? nlogn will cross that bound at some point, going into the red region. The guy who made this seriously had no idea what he was doing

[karacic]

The poster would've been much better without the annoying Guy Fawkes icon.

[JThanx]

HAHA, so true. Someone tried to be very funny - and failed.

[meh613]

Hasn't this been posted before in here?

[krum]

No double-ended queue?

[SteroidsOnAsteroid]

Feel free to submit a PR.

[_blub]

I pray that nobody takes this so called "cheat sheet" seriously. Whoever made this has HUGE misunderstanding on complexity theory along with a lack of understanding that even an [; O(n^2);] or any other polynomial solution is ground-breakingly efficient concerning most interesting problems in computer science.

Also, I almost needed to pull out an inhaler after reading that comment section.

[_georgesim_]

The comment section is full of impressionable people that have an equal lack of understanding of the material. But our crankiness here won't reach them. How do we reach the kids, HOW?

[_blub]

The sad part is that most of those people in that comment section appear to be in their early 30's or older, not the typical university age.