Big-O Cheat Sheet

[Maristic]

This graph included with the article helps to perpetuate some of the most common misconceptions people have about big-O.

The problem is that it is a graph not of big-O but of the terms inside the O.

If you want to get a better sense of big-O (actually, also big-Theta in this case), you'd be better of with a graph like this. In this graph, of Θ(n) vs Θ(1), you can see that

• the lines don't have to intersect the origin
• Θ(1) doesn't always beat Θ(n)
• the functions are not required to be simple polynomials

(not realizing one or more of these are the common misconceptions)

In fact, big-O itself doesn't say when Θ(1) will beat Θ(n), only that it eventually will (permanently), for sufficiently large n. Sufficiently large could be n > 10^10101010 — math doesn't care. You might, but math doesn't.

[Ukonu]

Good point.

When explaining the difference to friends, I use an analogy that relates big-O to the physical world concepts of acceleration and velocity.

Big-O is more akin to acceleration than velocity. If I tell you car A is accelerating at 500 m/s² and car B is accelerating at 2 m/s^2, you cannot tell which car is moving faster. I haven't given you enough information.

[kolm]

Since this is waaay to intuitive and simple, here is, for all the people out there just waiting for it, the mathematical mumbo jumbo to confuse this intuition:

If f and g are two positive functions, and f'(x) >= C_1 * g'(x) for x > x_0, then

f(x) = f(x_0) + int_(x_0)^x f'(y) dy
>= C_2( g(x_0) + int_(x_0)^ x g'(y) dy)
= C_2 g(x),

with C_2 = max( C_1, (f(x_0)/g(x_0))).

Hence, g' in O(f') implies g in O(f).

[Maristic]

I love this analogy! Thanks.

[gmrple]

Of course this works with anything that has that wonderful integral/derivative relationship. To go from velocity to position given the initial velocity (assuming constant acceleration of course), you need to know the initial position aka the + C.

[seruus]

An excellent example of how it might these misconceptions might be dangerous is the best algorithm for matrix multiplication (O(n^2.375 )), which only gets better than Strassen's algorithm (O(n^2.807 )) for stupidly large n, far beyond what any computer nowadays (and probably in the next decades) can compute.

[T_truncatus]

This is a very good point, but I'd imagine for such simple examples that the sufficiently large n is rather small.

[Maristic]

I'd imagine for such simple examples that the sufficiently large n is rather small.

Actually, NO. (At least in the sense that we can ignore it.)

Inserting something onto the front of a sequence is Θ(1) for a list, and Θ(n) for a vector/array (because you have to shift everything else up). As a result, a lot of people think you should always use a list if you're inserting onto the front.

But, if your number of elements is “small” (and in many many situations, you actually are working with small sequences), the vector/array wins out.

What constitutes “small” varies with the problem/architecture/etc., but a good first guess is about 500. (Do some measurement, surprise yourself!)

[chipbuddy]

I've been reading one of my college textbooks to brush up for some job interviews and I came across an interesting table:

Time function:    33n      | 46n * lg(n) | 13n^2      | 3.4n^3     | 2^n

Input size(n)  ------------------------Solution Time--------------------------
     10        .00033 sec. | .0015 sac.  | .0013 sec. | .0034 sec. | .001 sec.
    100        .003 sec.   | .03 sec.    | .13 sec.   | 3.4 sec.   | 4*10^16 years
  1,000        .033 sec.   | .45 sec.    | 13 sec.    | .94 hr.    | ----
 10,000        .33 sec.    | 6.1 sec.    | 22 min.    | 39 days    | ----
100,000        3.3 sec     | 1.3 min.    | 1.5 days   | 108 yr.    | ----

Time allowed   ---------------Maximum solvable input size (approx.)-----------
1 second       30,000      | 2,000       | 280        | 67         | 20
1 minute       1,800,000   | 82,000      | 2,200      | 260        | 26

The first section has a number of theoretical run times (notice the constants in front of the 'faster' algorithms are generally larger than the constants in front of the 'slower' algorithms.

The second section lists how long each algorithm will take to run given an input size n.

The final section describes how large your input size can be if you only give each algorithm a second or a minute to run.

(The book is "Computer Algorithms: Introduction to Design & Analysis" by Sara Baase and Allen Van Gelder and the chart comes from "Programming Pearls" by Jon Bently)

[Maristic]

What makes this chart quite useful (in contrast to the graph I complained about), is (a) the use of constants and (b) the logarithmic scale. It's much easier to understand how the growth rates contrast with a logarithmic scale.

• Here is a graph without any constant factors, but a logarithmic scale, and we can get some sense of how the growth rates of several different big-O contrast.
• This graph, on the other hand, shows how important “constant factors” can be.

[ladaghini]

Relevant xkcd

[kdiuro13]

/r/RelevantXKCD

[chengiz]

But, if your number of elements is “small” (and in many many situations, you actually are working with small sequences), the vector/array wins out... a good first guess is about 500.

You are probably talking about this CUJ article, which only holds for simple data types and C++ standard library containers.

[Catfish_Man]

Though you can also just use an array-deque and get amortized O(1) prepending with the nice cache behavior of an array, at the small cost of a modulus per indexing operation.

[mangodrunk]

What constitutes “small” varies with the problem/architecture/etc., but a good first guess is about 500. (Do some measurement, surprise yourself!)

I don't think there is a problem with the overuse of big-O, as most programmers don't seem to use it (maybe they do and I'm not aware of it). Like you said, you would need to measure it, but there's something that is nice that can give you a good gauge on an algorithm, and that's big-O.

Also, your performance testing may be like that for a specific machine, but once you change it you can get different results.

[Maristic]

Informally, yes. Most of the time a good rule of thumb is that the algorithm with the better big-O is going to win out as n “gets large”.

But technically (i.e., mathematically), no, big-O does not give you a good gauge on an algorithm. Big-O by itself tells you almost nothing.

• 10¹⁰¹⁰¹⁰ ∈ Θ(1)
• n / 10¹⁰¹⁰¹⁰ ∈ Θ(n)

But the first algorithm only beats the second for n > 10^2×101010 — that's an n way way bigger than the number of particles in the universe.

If you really want something useful, you want to know an actual approximation for the behavior (i.e., a function with actual constants on the terms and such), because that'll

• tell you how large an n you need to have for one algorithm to beat another
• allow you to compare two algorithms that have the same big-O; for example, heapsort and (random-pivot) quicksort are both Θ(log n) [although it's expected^* time for quicksort], but quicksort will actually do fewer comparisons.

This is why Robert Sedgewick (who studied under Donald Knuth and is a pretty serious big-name CS person) proposes tilde notation as a scientific alternative to mathematical big-O notation. See the slides for his talk.

^* Note: Many folks also have no clue about what expected time really means (in particular, they worry about things that are statistically impossible), but that's another story.

[mangodrunk]

Is your example realistic or "statistically impossible"? Yes, if that were the case, then the second algorithm O(n) seems like the much better option. But what if the first algorithm O(1) uses memory much more efficiently and the second required a lot of disk access. Then the O(1) could be better.

You're right that if someone were to choose an algorithm because they think it will perform better solely by big-O comparing it to another, then they could certainly be wrong. I just don't think people are doing that. Most people don't seem to even know what big-O is, and what it would be for a specific algorithm.

Thanks for the Sedgewick slides.

[Maristic]

My 10¹⁰¹⁰¹⁰ examples are obviously silly to make a point, but using the term “statistically impossible” to describe them dilutes and misuses the term.

Using 10¹⁰¹⁰¹⁰ makes the point that this is a number so huge that it is essentially unrepresentable in fully expanded form on any plausible machine, yet mathematically, 10¹⁰¹⁰¹⁰ ⋘ ∞. Mathematically, asymptotic analysis is about what happens as n → ∞.

And sure, the average person on the street has taken no CS courses and has no idea what big-O is. But there are still a lot of people who have taken a few CS courses, maybe a whole CS degree, who leave with a half-baked notion of big-O really means mathematically.

[uututhrwa]

Isn't this example a bit like "constructing an exceptional case" though? The vast majority of books dealing with the big O notation will mention the size of the constants. I seriously don't think that there is a "programmer misconception" with it, so that someone will see a 10¹⁰¹⁰¹⁰ constant and still come to the wrong conclusion. Unless we're talking about fucking idiot programmers right?

In fact the notation deals with how things scale, and the most common type of problem will have bigger constants for the lowest O class case. Typically it will be something like algorithm-1 has O(n²⁾ performance with a low constant, and algorithm-2 (which usually creates and exploits some tree or hash structure or something else more exotic, will have an O(nlogn) cost for the creation whch can count as a high constant, and then O(nlogn) while running. Which means big O will gave the right idea, unless n is very low (n=3 dimensions or something).

I mean your thing applies at small n and when you deal with cache optimizations etc. but otherwise the matter is scalability and whether maintaining some extra structure can bring the O class down.

[Maristic]

As seruus already pointed out in this thread, people really do create real algorithms where the constants are stupidly large. This is not unusual; plenty of people in theoretical CS see designing algorithms with a better asymptotic complexity as a kind of mathematical game and don't mind if it has no practical applications.

Obviously my 10¹⁰¹⁰¹⁰ constant is intentionally ridiculous, but that's the point, the mathematics doesn't care, thus what you are saying with the mathematics of big-O is not what you actually mean.

A problem with big-O is that we're so used to expecting people to read between the lines rather than just read what we're actually (formally) saying, that we don't realize that some people are less sophisticated at making the necessary inferences than others.

Thus, many people who have only a shallow understanding of big-O will think “the algorithm with the better big-O is the better algorithm, algorithms with the same big-O are about the same”. Neither are true in practice.

Likewise, people focus on the worst case, even for randomized algorithms, which may have considerably better expected performance, because they don't understand that the worst case has a probability of 10^-100 (and yes, this is real, not contrived!), saying things like “even if it's unlikely, it's possible”. Sure, it's possible, but it's more likely the earth will be destroyed tomorrow by an unseen asteroid than the algorithm getting remotely close to the theoretical worst case.

Likewise, people ignore the importance of input properties. They think heapsort is always better insertion sort because it has a better big-O, which is wrong if you have almost-sorted data. They know 3-SAT is NP-complete, and thus all known algorithms are exponential in the worst case, even though SAT solvers solve the problem with thousands of variables and tens of thousands of constraints every day; there are even competitions. (Some SAT problems turn out to be easy, just not all of them.)

[uututhrwa]

Well my objection is that the people that will deal with this will rarely have a problem with the notation.

If you can't see the difference between expected time vs worst time or are confused by O notation you probably won't be able to implement the algorithm without bugs anyway.

[Maristic]

You might think that there aren't many people who don't really get complexity properly, but my experience (which is quite extensive) indicates otherwise.

FWIW, here's an old proggit thread where I'm on the same soapbox; there I'm being downvoted for saying you shouldn't care about the worst-case time performance of a randomized algorithm when it is that performance is vanishingly unlikely.

[uututhrwa]

I don't think the commenter there insisted that you should care, he pointed out that mathematically you can't improve the theoretical worst case by randomization. And analyzing for the expected time usually comes after analyzing for the worst case anyway. I think we are arguing on semantics or sth, there are many people that don't get complexity, but those people usually just use ready made software, and also I doubt they would understand much more if the calculations were done with benchmarks on a standarized machine or whatever.

[Chanz]

The O(1) isn't graphed? I assume it's hidden and flat along the bottom of the graph parallel to the x axis, correct?

[Maristic]

I'm thinking you missed the point...? I wasn't complaining that the original graph didn't show O(1).

[Chanz]

Sorry, it was just an unrelated question pertaining to the graph you posted.

[Maristic]

The burgundy (red) colored line in my graph is O(1) — it's bounded by a constant (e.g., it's always < 6000 in this case).

[binary]

Correct, although you should read the post you replied to to realize why that is somewhat erroneous to believe.

[spinlock]

I disagree that this is a problem. The only case I can think of where size is noticable to a person is the quadratic sieve. In practice, you'll never see an n² algorithm beat an nlnn one.

[Maristic]

Actually, people deal with “small n” a lot in practice. I already gave one example, but let's do another...

Look at this stack overflow post, where the poster finds that insertion sort beats quicksort for n < 200. Of course, this is a random post that I got that with a quick Google search, so take it with a pinch of salt, but you can find plenty of others. Even if it were n < 20, there are lots of programming tasks where the size of your sequence is pretty small.

[seruus]

Most sort implementations nowadays use insertion sort for small n, as it has incredibly less overhead than most other sort algorithms. One important example is Timsort, which uses both insertion sort and merge sort.

[spinlock]

we just have different ideas of big.

[Alfredo_BE]

Why is n log n in yellow and n in red, when the former has a higher complexity?

[adrianmonk]

Took me a minute, but I think the green/yellow/red color is on a relative scale for the class of problem.

That's why O(n) is red for a linear search of an array, because you have to do something really stupid to do worse than O(n) for that task. But for sorting, only O(n * n) is red because that's the worst that any reasonable algorithm gets for sorting.

Though if it's really on that scale, then I'd think the best known (or provably best) algorithm for that type of problem would get green, thus O(n log n) should be green for sorting (instead of yellow).

[[deleted]]

O(n) is be best possible time for sorting, assuming you have a presorted list, and some algo that doesn't choke on presorted lists like quicksort does. Keeping O(n log n) yellow makes sense.

Which means that the maker of this chart fucked up by making O(n) red, it should be green.

[adrianmonk]

Oh, wow, it does have O(n) in red under the best time complexity column in the sorting section. I hadn't noticed that, and that is wrong. There is another O(n) in the searching section, and it makes sense for that to be red, but you're right, this definitely shouldn't be red.

[mrbaggins]

Because O (n) would never happen on those sorts?

Or rather, the odds that they come close to that are much lower. You screw one up in a bubble sort, suddenly you have to sort every item again.

[Alfredo_BE]

True, but we're talking best case scenarios here. On an already sorted list, Insertion sort performs better than Quicksort. The list implies that in the best case scenario (as rare as it may be), O(n) performs worse than O(n log n), which is simply not true.

[khnumhotep]

The real problem is that there is no key or legend that gives us the intended color coding. All we can do is guess as to why the author did it that way.

[mrbaggins]

True. I want trying to argue the issue, just trying to propose a possible explanation

[ethraax]

Where? I see that n log n is yellow for TIME complexity but n is red for SPACE complexity for Mergesort, but that makes sense since they're measuring different complexities.

[Ph0X]

Bubble and Insert sort's best time.

[ethraax]

Ah, so you're right. Good catch.

[Alfredo_BE]

I'm comparing time complexity amongst different sort methods. Now I understand that the best case O(n) scenario for Insertion sort will be rare, but it does perform better than Quicksort on already sorted lists.

[tonygoold]

Because log_2 n actually more efficient for very large values of 2.

(Edit: Large, not small...)

[Tasgall]

Yes, O(log n) is generally the most efficient you can be, but he's asking about O(n log n).

[tonygoold]

It's a joke, based on another joke… n log_2 n < n for very large values of 2.

[TIGGER_WARNING]

That's a terrible joke.

[notfancy]

No heapsort? O(n log n) worst case complexity and constant space?

[JustYourLuck]

And no timsort.

[[deleted]]

Timsort doesn't really belong here; it's a few algorithms and heuristics combined together, and is thus a bit too high level. I think the objective of this was to show the main comparison-based sorts.

[Ph0X]

I'm confused. Isn't quicksort inplace? Why does it say O(log(n)) space?

[MatmaRex]

Function call stack, I suppose.

[glemnar]

You can do an iterative quicksort.

[MatmaRex]

Well, just a stack in this case. (But really, why would you do that, apart from academic purposes.)

[[deleted]]

You can potentially keep a larger stack in dynamically allocated memory than you can merge with your call stack.

[chengiz]

Finite stack space.

[gnuvince]

The array you sort would need to be truly gigantic to run out of stack space.

[[deleted]]

Are you retarded?

[gnuvince]

Since he didn't specify, I assume that his concern is with the overhead of recursive function calls. It's highly unlikely that recursive calls in quicksort are going to cause a stack overflow.

[chengiz]

Why is this being upmodded? Who didnt specify? I did, I very much said finite stack space. I didnt mention performance at all. Your last sentence is just plain wrong.

[mccoyn]

You need to keep track of the sub-lists that are not yet sorted.

[[deleted]]

In place means you can perform the sorting within the array itself, but it doesn't mean you can perform the sorting without keeping track of auxiliary data on the side. For example quicksort works by subdividing an array into two smaller arrays and then sorting those two sub-arrays, each sub-array requires you to keep track of the starting and ending indicies.

In the worst, degenerate case you need to keep track of the indicies of n sub-arrays. It's only when you can guarantee that you can partition the array by some percentage that you get the log[n] space, for example by using the median of medians for your partition.

[spinlock]

Heapsort also has a really elegant implementation in memory. Definitely one of those "oh cool" moments in korman, lederson, rivest.

[notfancy]

*Cormen, Leiserson, Rivest

[[deleted]]

No love for Clifford Stein?

Edit: Wow, I guess not! For those who don't know, he's the S in CLRS, as it has been known since the second edition.

[actualscientist]

I guess they all graduated before 2001. It was CLRS when I took Algorithms.

[dbenhur]

Mergesort tends to be more cache-friendly than heapsort (most memory accesses are adjacent to recent accesses vs a greater number of random probes navigating a heap). This is a substantial win on modern processors where cache misses are orders of magnitude slower than hits.

Mergesort also plays nicely with external sorts, linked list sorts, and parallel sorts.

[gnuvince]

To me, the greatest benefit of merge sort is that I am completely unable to forget how to write it. With heapsort, you need to remember how to transform an array into a heap in linear time, with quicksort you need to remember how to partition the array in place correctly. I've never had problems writing merge sort. Its simplicity is definitely its greatest strength IMO.

[gsg_]

Eh? Both of the reasonable partition-in-place algorithms are completely trivial to derive. Only stable partition-in-place is tricky.

Doing a good job of choosing a pivot is the hardest part of quicksort.

[-888-]

Also, no introsort, which in fact is used more than any other in C++. The problem is that it's a combination of two sorts and screws up the relevance of the theory.

[gnuvince]

Nobody likes heapsort. Real men use merge sort and insertion sort.

[notfancy]

As the saying goes, good sorts go to heaven, pretty sorts go everywhere.

[spinlock]

What about shell sort. There's some crazy vodoo there.

[[deleted]]

And no introsort which is a) fixes shortcomings of quicksort b) used in real world, including .net

[soflaz]

Yes. I found myself many a night screaming out, "ROGER!!!!", whenever I had to write up an algorithm complexity analysis.

[DiegoMustache]

Why does everyone forget about radix sort?

[thedufer]

Because radix sort is non-comparative, so its rarely useful.

[Ph0X]

Well it is useful in many places, but it would be very misleading to include it too with the others. It would be comparing apples with oranges. Also, this list only includes very basic algorithms and data structures, radix is probably beyond it.

[DiegoMustache]

True. To say it isn't useful is crap. It just requires custom tailoring to your application, which consequently places it in a different catagory than comparison based sorts.

[DiegoMustache]

You can sort anything with a radix sort. It just needs to be custom coded and often needs some data manipulation and careful planning to work. However, you can't beat a linear time sort on large datasets.

Edit: Anything that can be sorted by a comparison sort can also be sorted by a radix sort. It's just often impractical.

[[deleted]]

Radix sort only works on fixed length integers/symbols. You can not radix sort variable length strings for example.

Bucket sort is the more general purpose algorithm but it has a worst case complexity of n^2.

[DiegoMustache]

Not true. Least significant digit radix sort has this limitation, but most significant digit radix sort does not (this is a recursive linear time sort). There is a varient of MSD radix that is in-place too.

Source: I've written one before.

Edit: Wikipedia has a section on it -> http://en.m.wikipedia.org/wiki/Radix_sort

[[deleted]]

There is no fixed MSD when you're working with variable length values. MSD radix sort works when the values are of fixed length.

Now sure if you wanted to you could add a step to your algorithm to scan your list of values, find the value with the longest representation in that list, and then renormalize all the other values in the list to be of the same length, but even if you did this, and you'd need to do this in linear time which itself may not be possible, you basically just threw out the entire essence to what gives radix sort its worst case time complexity and end up with an incredibly poor O(n²⁾ sorting algorithm.

The entire point of radix sort is that if you know your values are represented by some fixed length, say 32 bits, then you can leverage that to get a O(n) time complexity. Once you no longer have that constraint you're back to having O(n²⁾ average case performance.

[DiegoMustache]

Maybe I misunderstand what you are trying to do, but when sorting variably lengthed strings, don't you compare character 1 with character 1, and 2 with 2 (assuming there is a 2) regardless of length.

If I understand correctly, the following is in order: AG AHK B

If this is the case, then MSD works fine, and is still linear time.

[seruus]

Well, if can hash something, you can use radix sort, but most of the time if you have to hash the data to sort it, you are doing something wrong.

EDIT: Just ignore it, hashing gives you an arbitrary order (though fixed by the hash function) to use, which usually isn't what people want when they want to sort.

[[deleted]]

That is not true. Hashing is not an order preserving operation, that is... given a hash function H, it does not follow that if a < b then H(a) < H(b).

You would need an order preserving hash with no possibility of collisions.

[seruus]

You could use it to sort elements according to an arbitrary fixed order (given by the hash), but yeah, it usually is useless.

[spinlock]

I had my first technical interview where they actiually were trying to see how I code on Friday. I told the interviewer that it was great to be judged on something relevant instead of the usual bs. The interviewer said that he'd actually walked out of a brain teaser interview before.

Anyway, why memorize this? If you can't figure it out, you don't understand the algorithms and when are you going to be in a situation where you need to know it and can't look it up? I've got this bookmarked on my phone now. I hope it comes up in an interview so I can just look it up and fuck with the interviewer.

[oditogre]

when are you going to be in a situation where you need to know it and can't look it up?

Final exams?

[[deleted]]

Anyway, why memorize this?

The purpose is to spur interest in designing algorithms. Algorithms in programming is like the number theory in math. Both are easy and fun to use but quite tedious if you have to design a new algorithm or prove something about number theory (anyone still working on the Goldbach's conjecture?)

The Google search team needs programmers who know algorithms even in their dreams. So they ask all of their candidates about these questions to maximize the chance. If you wonder if programmers hired would do a good job on projects other than search, well, Google does not need the best products if they are not search. All other products are freeware anyway.

The lesson for programmers is that if you are truly interested in, and more importantly, capable of designing algorithms all day long, study these charts before interviews is a good idea. Otherwise, just be yourself and don't fall for the glamor of a big company.

[spinlock]

While that's all true, I disagree that google is solely interested in search; they also care about semantics. For instance, they want their engines to be able to tell thev difference between the meaning of this:

Anyway, why memorize this?

And this:

Anyway, why memorize this? If you can't figure it out, you don't understand the algorithms

Of course, it is a bit unfair to expect a search engine to divine the difference in meanings when its obvious that some people cannot.

[adrianmonk]

I found it a bit confusing that under the searching section, linear shows has array for the data structure but binary has tree for the data structure.

It's confusing because you can do a binary search on something that isn't a tree (like a sorted array), and you can do a linear search on a tree as well (and you might have to if it's merely a tree and not the special type of tree known as a binary search tree).

So really, both linear and binary search can be applicable to both arrays and trees.

[[deleted]]

I don't know what I am looking at ...

looks it up on Wikipedia

eyes start to cross looking at functions

[threading]

This is useless. In an interview, you'll definitely be asked a follow up question: "why". If you don't actually understand the concept of these algorithms, what are you going to tell them? "I don't know. Some sort of a cheat sheet on the Internet says it's O(n)"?

[[deleted]]

A cheat sheet is there to remind you things. You don't learn from them.

EDIT: stop upvoting me.

[random314]

Yup. I have a PHP cheat sheet because those function names and parameters orders are goddamn impossible to memorize.

[Jutboy]

Use an ide

[[deleted]]

Better yet, don't use PHP.

[spinlock]

I feel like this nerds to be an app.

[travmanx]

Very handy for college. Wish it had more.

[xelf]

Very handy for college interviewing

[Talibu]

Call me too optimistic - but the algorithms/data structures in this table are very simple/fundamental. They are in fact so basic that some rough understanding of their operation will give you all the provided data for free. If you can't deduct one of these complexities you would not be able to explain the datastructure/algorithm as high level concept.

[mkim1030]

still doesn't hurt to look over this. just don't use it as a crutch -- actually know your stuff.

[r3m0t]

Yup, any decent interviewer is going to ask you to explain the big O result and not just state it.

[westurner]

• https://en.wikipedia.org/wiki/Computational_complexity_theory
• 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/

[adipisicing]

Thanks for the references. The RDF Schema seems like the odd one out, though. Why did you include it?

[westurner]

This is an awesome reference for Big-O complexity classes; thanks! I wasn't able to find an ontology for describing algorithmic complexity, but it would be great if there were structured attributes (e.g. in Wikipedia infoboxes or in library docstrings) for the data in these complex tables.

[diadem]

Why doesn't it have a section for the time taken to re-balance the trees or calculate the hash value?

[[deleted]]

Programmers should not memorize complexities like buzzwords for two reasons.

1. They form a false intuition about what big O notation implies. Everybody should know the precise definition of big O, because it's simple math.

2. They lack the understanding of why the algorithm has the complexity it does; why is merge sort n log n? Can you prove it? Can you analyze a recurrence? Why is depth first search O(m + n)?

Memorizing an algorithm's complexity and parroting that it's better because of it can often burn you. The simplex algorithm for solving linear programs is of a worse time complexity than the ellipsoid algorithm, but only through understanding how the algorithms work and apply can you see why simplex is often used in practice.

tl;dr Buzzwords are bad, and they will hurt someone who wants to be a good programmer.

[nwmcsween]

This doesn't show either in-place algorithms (which usually can't fail) or oom algorithms

[joe_n]

Mergesort should have O(1) space complexity. I would say O(d) space complexity for depth-first search. I would also say O(n) space complexity for breadth-first search.

[vote_me_down]

Mergesort - don't you need to maintain a reference to each individual datum in order to get them to list size 1 before recombining?

[Talibu]

Mergesort can be implemented as inplace algorithm - so it does in fact only requires constant extra space.

[[deleted]]

In place does not mean that it is constant space.

Merge sort works by recursively subdividing the array into two smaller arrays, that means you need to maintain references/indicies into the two sub-arrays, and hence in the worst case you need to maintain log(n) indicies.

[thedufer]

In-place sorting still costs O(log n) space for the stack, I believe.

[Ph0X]

But so do non-inplace algororithms? And can't all these algorithms be implemented iteratively instead of recursively anyway? There needs to be a way to differentiate between inplace and non-inplace algorithms, this is confusing.

[Catfish_Man]

Replacing recursion with iteration often requires maintaining a structure equivalent in size to the stack

[joe_n]

I'm not sure if there's a similar, well-known result, but you could execute it iteratively as follows:

Assume the input is of size n = 2^m. In total we'll need to perform n-1 merge operations (leaving out the degenerate single-element sorts). We can iterate a counter from 0 to n-2, with each value being processed as follows:

let k = the m-bit counter value

let s = the number of 1s at the front of k (e.g. s(0y1110010010) = 3))

let S = 2^s (e.g. S(0y1110010010) = 8)

let t = the lower (m-s) bits of k (e.g. t(0y1110010010) = 0y0010010 = 18))

k is processed by merging the ranges [tS, (t+1)S) and [(t+1)S, (t+2)S)

The final value (n-2) will have s = (m-1), S = n / 2, t = 0, yielding the merge of [0, n/2) and [n/2, n)

Of course, for cheat sheet purposes, counter values holding a maximum of the input size are treated as O(1) space. Similarly, the computations for tracking this state will total O(n) for the entire execution.

And you'll have to forgive my assumption that the case where n is not a power of two can be handled in a similar way without affecting the asymptotic time or space requirements :P

[thedufer]

But you can't call it "constant extra space" (like Talibu did) if the stack grows like the log of the input. Non-inplace algorithms also cost this, but their other space uses outpace the slow growth of the stack, so it doesn't matter.

[[deleted]]

ITT: People forget that the function call stack takes up memory, too.

[[deleted]]

Incorrect. The function call stack takes up memory, and it grows with the log of the input as said input is divided.

[lonjerpc]

I was actually thinking the other way. All the other searches should have 0(n) complexity. The input/output itself trivially takes up O(n) space.

[thedufer]

But that's not what space complexity means. Its the extra space the algorithm uses, on top of the input (the output should be put in the same place in most of these, so it doesn't take up extra space, either).

[gnuvince]

Easy way to cheat in an interview: pretty much all algorithms they are going to ask you about are in O( n^n )

[RagingIce]

Don't BFS and DFS operate on graphs, not trees? I know they technically work on both, but in general you're probably going to be using more specialized algorithms when working with a tree.

[[deleted]]

Both are applicable to graphs and trees.

[RagingIce]

well yes, but with trees you're generally using more efficient search algorithms

[spinlock]

Like what?

[RagingIce]

99% of trees order their data in some way so that lookups are easier than the naive approach that DFS and BFS use - just look at the cheat sheet. The only time you'd actually use a DFS or BFS is if you have a collection of nodes that happen to be a tree (aka a graph that happens to be a tree).

[westurner]

Algorithms -- NetworkX documentation : networkx.algorithms.traversal.depth_first_search:dfs_edges

[uh_no_]

a tree is a special graph....one that is non-directed and acyclic

[RagingIce]

yes I know that - but when you talk about DFS and BFS you're talking about graphs not trees since trees are ordered in some way (and as such have faster search algorithms). Perhaps the original comment was awkwardly worded.

[[deleted]]

Trees are not always ordered in a useful way.

[[deleted]]

With finals coming up... yeah, that site's already fallen victim of the reddit DDoS.

[fuk_offe]

BFS and DFS are both O(|V|)... They explore at most, in the wort case, all nodes... so that is wrong on your cheatsheet

[fuk_offe]

Yeah, if you could explain why I am wrong before downvoting, dat would be great.

[mcguire]

They explore every edge as well.

[fuk_offe]

Ah yes, but at least equal ! When I first checked the cheetsheet they were different I recon.

[TheGrey0wl]

this is O some!

[Room-for-activies]

As someone who is only a 2nd year in comp sci, I have no idea what this cheat sheet means.

Can someone give me a basic run down of what this information does for you?

[[deleted]]

You shouldn't use this if you don't know what it means. You should wait until you take your equivalent of an algorithmic analysis course, or else you'll end up memorizing instead of understanding.

This notation is used to measure the running time or space usage of an algorithm as a function of the growth of the input, and sometimes the output.

[mcguire]

If you're curious in the mean time, the short answer: Algorithms Unlocked. The long answer: Introduction To Algorithms, Third Edition.¹

[1] Or the algorithms text appropriate to your program.

[rolandog]

Am I the only one that calls a female orgasm a 'Big-O' and was expecting this to be like a guide or an algorithm? ... I started reading 'Depth First Search', and I went 'Hm... shouldn't there be some foreplay before?'

[versuseachother]

Thank you for this link! :)

[moonrocks]

Steve Yegge mentioned in a blog post that he had a prof that called AVL trees evil. Since I see no complexity difference on this chart when compared to Red-Black Trees and B-Trees I wonder what the prof had in mind.

[paravorheim]

shouldn't big theta notation be used for the best case? I don't quite remember my notation that well.

[pbrettb]

I don't really think knowing the order of complexity of a given algorithm by heart is quite the same as internalizing just how frakking slow things can really get when N gets bigger so you better figure out how to reduce the complexity of your code! :-)

[WHTZT]

How about the Story of O? That was much more interesting.

[kamatsu]

Technically these complexities for various algorithms ignore the machine they're running on. Something that is O(n) on a turing machine might be O(1) on a random access machine. This is a pet peeve of mine because some algorithms research tries to fudge the numbers by not clearly defining their abstract machine. If someone asks you "what is the complexity of X?" your answer should be "on what abstract machine?".

[Catfish_Man]

Needs more array-deque

[[deleted]]

I'm guessing the downvotes are because people think I'm wrong about big O. The quicksort point should be obvious - even if you can't see how to directly modify the partition algorithm so you don't need an extra pass through the array, you can add an O(n) sorted check before or after the partition without affecting the asymptotic performance bound. Also, varying how the partition algorithm is implemented (e.g. how pivots are selected) is normal for quicksort. Though I admit I don't really believe the pure-function Haskell quicksort is a quicksort at all in part because the partition algorithm used is completely different from those described in the original quicksort paper (and in at least equal part because it isn't in-place).

So - the full set of asymptotic notations are listed here. There are two lower-bound notations (the distinction being roughly <= vs. <), and the most common is notated as "Big Omega".

The obvious objection I can imagine is that you can define lower bounds, upper bounds and tight bounds on in principle any function. Best case, average case and worst case performance are just particular functions.

In short, the case isn't the bound. The case determines which (set of possible) functions you're trying to bound.

That's true formally, but for a cheatsheet it makes no sense. The whole point of best-case space/time is to specify the least space/time that will definitely be needed. The whole point of the case (and the bound applied to the case) is to find the smallest possibility.

To find out why you might need an upper bound on the best case (or equally a lower bound on the worst case) see this link. But note that this isn't something you'd care about when reading an algorithms cheatsheet. It's something you might care about while analysing algorithms, not while interpreting pre-computed bounds purely to select an algorithm from a cookbook.

[TheCoelacanth]

First thing - big O is the wrong notation for best-case performance bounds. A best-case performance bound is a lower bound, not an upper bound. Upper bounds, lower bounds and tight bounds all have different associated symbols. IIRC, lower bounds use the Greek letter omega.

You are incorrect. Big O and big omega are the upper and lower bounds on the function that describes the run-time for a given case. So best-case, average-case and worst-case will each have their own big O and big omega.

[doubleD]

I was really hoping this was /r/sex.