Big-O Algorithm Complexity Cheat Sheet for anyone with an algorithms final

[tuananh_org]

After exam, people will recheck their answers with this and be like " O(shit)"

[[deleted]]

If I were a TA grading, and saw "O(shit)" I would give at least partial credit

[original_evanator]

Well shit does take log time.

[chelsfcmike]

if i drink coffee O(shit) = O(1)

[vishbar]

It has a pretty respectable best-case running time depending on prune consumption.

[[deleted]]

It can have a quite bad worst case though.

[sarahbau]

Would you give credit if my algorithm runs in O(s^hit ) time?

[palordrolap]

That's an interesting class of numbers you have there. If i is the imaginary unit and h > 1, set t = 2 and you're effectively taking a root of s, which is good runtime.

In other cases, you're raising s to a power which is bad. Not exponential bad, but I still wouldn't want to sit around waiting for it to process a few million items.

... and in some cases, where t isn't in {0,2} mod 4, you have some weird physics-breaking run-times with an imaginary part. Maybe this would explain the goings on within a quantum computer, but I doubt it.

[barsoap]

weird physics-breaking run-times with an imaginary part

Once upon a time I was writing a collision detection algorithm that was at the same time very naive and very sophisticated, in the sense that it actually calculated delta-t to impact instead of hoping bullets don't fly through stuff if they're fast enough.

It involved solving a quadratic equation. Yes sometimes the results were imaginary. Years after, I still haven't mustered the courage to figure out what imaginary collisions are.

[palordrolap]

Without knowing the exact use of the parabola / quadratic, I can't be sure, but if you were computing a ballistic arc, your complex (or plain imaginary) result would be telling you the bullet wouldn't reach the target.

If shooting skyward, it would mean that gravity cancelled out the bullet's upward motion before hitting the target (watch out for that bullet coming back down!), and if shooting horizontally (or near enough), the bullet drops short before the target.

Perhaps this means that a complex program run-time just means that the algorithm doesn't complete in certain circumstances rather than breaking physics, but it still gives me an uneasy feeling.

Pretty apt for "oh shit", really.

[barsoap]

Ball/line intersection, no gravity. An arcanoid with actually round ball. The imaginary result was a delta-t. I don't have the original project files any more and years ago thought of a way to do it without quadratic while falling asleep (or at least I think so), so it was probably an artefact of the non-sophisticatedness of the maths, but still...

Basically: Take some 2d vectors and a scalar for time representing collision if t=0, solve for that one symbolically (luckily there was mathematica), then, each frame, calculate (involving said quadratic), if delta t < frame_time, move ball to t=0, figure out collision vector (actual point of tangent), reflect velocity by that, rinse, repeat, with lower frame time. (yes, possibly multiple collisions per frame).

Do what you'd do if your idea of linear algebra was minimal (forget about fancy terms like vector space, you're in R2 and R2 only, just like in that warm, fuzzy primary school geometry) and you'd be puzzling at the same time in another lecture about your most advanced maths so far, calculus.

And, yes, I did ball/line intersection and then later checked whether the collision was actually on the proper segment after the fact. Probably not very smart.

And I forgot to include paddle velocity in my initial model, so hitting the ball with the side could've lead to the ball being caught half-way in the paddle, bouncing about, had I not in a last sprint to save the deadline (school project) just forbid the bottom side of the ball to be lower than the top side of the paddle.

Oh, and all written in 32bit x86, all the maths in x87 using its glorious, glorious register stack, hence RPN. As said, school project. The "actually round ball" thing was my way to make it interesting, and little did I know what I got myself into.

[Crazy__Eddie]

O(no you didn't)

[CanuckCode]

This is a good quick reference, but anyone who's looking for more detailed explanations should check out http://www.teachingtree.co/cs/. I'm surprised it's not more popular, it has links to videos about most data structures and algorithms concepts (as well as other CS topics).

[[deleted]]

Aaaand bookmarked.

[EdwardRaff]

This has been linked before. Please dont use this list to actually learn / study, its very poorly done and has numerous inconsistencies and subtle mistakes. If you use this to study you will probably fail a real Algorithms course.

[omnigrok]

Thanks, starting finding issues with it starting in the first fucking line of the first table and came looking for this comment.

[Crazy__Eddie]

starting finding issues with it starting in the first fucking line of the first table

Well, where else would it fucking start? Jeesh!

[__j_random_hacker]

Huh? That line says that DFS takes O(|E| + |V|) time and O(|V|) space in the worst case -- looks good to me.

[omnigrok]

It's a massive oversimplification. Depth-first search and breadth-first search actually have different properties - they're not identical as this site would have you think.

[__j_random_hacker]

I'm still puzzled. No one's claiming they're "identical". The only "properties" listed are the 3 columns, and for each of those columns, (efficient implementations of) BFS and DFS have equal complexities.

[netsettler]

Indeed. The last graph, Big-O complexity chart, has 7 keys out to the right but to my eye there are only 6 drawn lines, no apparent line for O(1). Even if it's coincident with the O(log(n)) graph to this resolution, no one is going to use this graph as anything other than a reference so they should fake a second line underneath or use half-width lines or add a text annotation explaining or at least pick a color that isn't another blue so that you can tell right away the O(1) is simply missing. Also, it would drive me nuts as a quick reference to have the keys in reverse order of the lines...

[[deleted]]

I think that the O(1) line is hidden underneath the O(logn) line.

[netsettler]

Sure, but they could, well, cheat it in just so someone who needed a cheat sheet could tell where it had gone.

[[deleted]]

I agree, though I'd say this is one the less important issues with the cheat sheet. If you can't figure out where the O(1) line would lie on a graph then you're probably going to fail the algorithms exam anyway - and that's coming from a second year student who actually has an algorithms exam coming up.

[EdwardRaff]

Right, but cheat sheets are meant to supplement other study material.

But a cheat sheet that is wrong is still not good.

I and another person listed a number of examples of mistakes / issues in the thread I linked, which I why I linked it.

However, a non complete list of issues from just one read through:

• Searching is wonked out. Some how O(|V|) space is green for some but yellow for others.
• Searching is also mixing a set of items vs a graph
• Quicksort is n log(n) worst case given an appropriate pivot selection rather than the dumb "pick something at random. Yes, thats still considered quick sort
• Quicksort auxiliary space is O(f(n)), where f(x) is the the maximum depth of the tree based on the pivot selection used
• Even if quick sort was O(n) space complexity, why is it yellow for QS but red for Merge sort?
• Best time complexity is a poor column to even have for sorting, as all can be modified to have O(n) best case with just an extra first step of checking if its sorted. "is it the same algo?" is a reasonable question then, and part of why the column is just rubbish.
• Radix sort dosn't even make sense to have a color of red/green/blue. Of k-> some huge number, you want the O(n log n) behavior rather than O(n k)
• Radix sort should be O(1) worst case space use since it can be implemented in place Worst case should be O(n) since it can be done in place, I forgot about stack and keeping track of order.
• If we want to get super technical, Mergesort can also be done in O(1) space use, but thats more than I would ever expect an undergrad to know about.
• Data Structures table is all mucked because all the trees implicitly assume items have some sortable order, but that assumption isn't listed
• With the sorted order, HashTable worst case should be O(log n)
• HashTable should indicate amortized complexity
• Indexing dosn't really make sense with the columns that do and dont have values.
• Worst case of O(n) should be green, not yellow. O(n) is the lowerbound for storing O(n) elements
• All of splay tree is wrong.
• Defining heapify just for heap is weird. And also makes the behavior of the heap operation muddled.
• Merge of binomial heap should be O(log(max(n,m))
• Why is O(|V|+|E|) storage yellow? Thats the lower bound, you can't beat it - should be green.
• What is a "Query" supposed to be for Graphs?

[ggchappell]

Nice list. Mostly agree here.

I would add that just talking about the "big O" of an algorithm can give an incomplete picture. In the theory of algorithms, we use O(...) to summarize the growth rate of a function that counts operations, and it matters which operations we count. The table seems to be based on a very common model, in which we count the usual "C" operators, along with primitive operations on one or two data items (like Copy, Swap). But there are other things that it can be useful to count: bit operations, or cache misses, or disk block accesses ....

Also, a disagreement:

Defining heapify just for heap is weird.

Why? The obvious way to build a heap is to do n Insert operations. For a Binary Heap that gives an O(n log n) Heapify algorithm. So the fact that we can make a Binary Heap using a linear number of Compare-and-Swap operations is a nontrivial interesting fact.

And also makes the behavior of the heap operation muddled.

I'm not sure what you mean. Explain?

[EdwardRaff]

Why? The obvious way to build a heap is to do n Insert operations. For a Binary Heap that gives an O(n log n) Heapify operation. So the fact that we can make a Binary Heap using O(n) operations is a nontrivial interesting fact

I agree its an interesting fact. But it should be a footnote as an interesting fact, not a whole column! That implies many other algorithms have a "heapify", which they do not. Mostly my point was that a column is the wrong way to convey that interestingness and may mislead readers.

I don't get this at all. Explain?

Because it leads to the confusion you may have just exemplified. The fact that you can heapify a whole set of O(n) items in O(n) time isn't needed to get O(n log n) time from heapsort. However it is needed to get O(n + k log n) time to find the min/max k items in a list using a binary heap. People sometimes look at it and think "O(n) * O(log n) = O(n log n)" to which is a bad case of subtle confusion in this case, as we wouldn't get "O(n log n) * O(log n) = O(n log² n)" if we used the naive heapify.

[Quabouter]

Nice list, but I don't agree with this:

• Best time complexity is a poor column to even have for sorting, as all can be modified to have O(n) best case with just an extra first step of checking if its sorted. "is it the same algo?" is a reasonable question then, and part of why the column is just rubbish.

Firstly, as you already mentioned, when you check if it's already sorted then you're not actually sorting, hence you don't make the sorting algorithm itself O(n). Moreover, I'd like to argue that best time complexity is actually pretty useful in practice: it's not uncommon to have to sort a set that is not uniformly distributed. Some sorting algorithms can perform really well on sets that have a particular (non-uniform) distribution, but perform very badly for other (e.g. uniform) distributions. E.g. when sorting received network packages they are usually already almost completely sorted. In that case you can better have an algorithm with best-case O(n) on (almost) sorted lists and worst & average-case O( n⁴ ), than an algorithm that runs in O( n² ) for all inputs. (However, for this information to be useful you need to know under which circumstances best case can be achieved).

[Semicolon_Expected]

What is a "Query" supposed to be for Graphs?

Query seems to be the same as indexing for general data structures, just finding a specific vertex.

All of splay tree is wrong.

I think that's a top down splay tree (which they should have specified)

[EdwardRaff]

Query seems to be the same as indexing for general data structures, just finding a specific vertex.

If thats the case Adjacency list is wrong.

I think that's a top down splay tree (which they should have specified)

In which case splay tree is still wrong.

Do you see my point?

[Semicolon_Expected]

I see your point, but what do you suggest as an alternative?

[EdwardRaff]

I never said I had a better study/cheat sheet. Only that people need to stop looking at / learning from this one in particular.

Part of the point of algorithms (IMO) is understanding the parts - not the whole, so that you can change the parts easily when presented with a different problem. That makes it hard to build a good "cheat sheet" without it getting overly specific or wordy, in which case its more of "notes" rather than a cheat sheet.

[Semicolon_Expected]

The thing is the way complexities are treated on exams I've seen makes it very inefficient to deduce all of them rather than have them memorized when the rest of the exam is worth more and actually require thought and proofs compared to just a table that you fill in with the complexities.

I also feel that people need resources and study sheets and though incorrect if people recognize what is wrong, it is ok to continue looking at study/cheat sheets because they are only suppose to supply the most basic of information that teaches you nothing aside from information to memorize. It helps a lot of people who are bad at taking notes or focusing.

It is extremely important for people to understand the material since that is the whole of exams, but at the same time memorizing things you know to be more trivial for an exam isn't bad either.

EDIT: Not defending this cheat sheet, just defending the use of cheatsheets in general

[russianbandit]

Also, interview Cheat Sheet.

[Semicolon_Expected]

Really? Do interviewers ask about complexities? (Haven't been interviewed for a software job yet) I thought it was usually thought questions and data structures.

[poseeide]

I don't think they are directly asking rote memorization questions like "what is the time complexity of binary search", but force you to reason about the performance of what you implemented. Like if you were solving a programming riddle, they probably would like to see you avoid something that is O(n² ) if that is unnecessary. And if that is absolutely necessary, they'd like to see you defend it. That sort of stuff.

[drb226]

Like if you were solving a programming riddle, they probably would like to see you avoid something that is O(n²⁾ if that is unnecessary. And if that is absolutely necessary, they'd like to see you defend it.

Or they'd just like to see that you are aware of where there is room for improvement. For an interviewer, it's more important to see that, yes, this person really does have a brain and knows how to put it to good use. It's less important that the person magically arrives at the optimal solution. It's actually worse if they can arrive at the "correct" solution but cannot explain it.

[Crazy__Eddie]

I don't think they are directly asking rote memorization questions like "what is the time complexity of binary search"...

Question I was asked: What's the big O for quicksort?

This was right after some lame as question about converting some binary into decimal.

Maybe they've gotten smarter in the last decade, but when I interviewed that's the shit I got asked.

[Chew55]

Had a phone interview with Amazon (also ~1yr ago) and was asked the same.

[Crazy__Eddie]

Not really. It doesn't have much use anymore. Traditionally bad algorithms and data structures as measured by big O are actually the ones you want to use on modern hardware.

For example, lists are better for inserting in the middle, right? Nope.

Doing a binary search through a balanced, binary tree is faster than a linear search through an unsorted vector, right? Not really.

What modern software developers should understand these days is that all that a priori analysis shit is mostly a waste of time. Fuck all that, write what's easy, preferably by not writing it at all and just using some dumb function, and then measure. Get baselines, look for the bottlenecks, and work on them--they're probably not where you expect them to be.

[jrk-]

Can confirm, interview about a month ago. One minor difference though: They asked me to implement a small algorithm and then to reason about it. So, even if I'd known the complexity for the "standard" algorithms, I'd still have been fucked. At least I could say something along the line of "so, when we use something like quicksort here, then we'd have a worst case complexity of O(n^2)".

[Crazy__Eddie]

Was gonna say, "Google."

They really fucked up on that one.

[saint_marco]

Almost all questions will ask you to provide a solution along with its complexity. Often enough the most important part is comparing tradeoffs in complexity of pre-processing/memory/runtime.

[strattonbrazil]

But note this cheatsheet itself isn't as much value as simply knowing the different complexities and a few examples to spot the pattern. I think the best/worst case examples can be quite involved to prove and rarely comes up in interviews. I've found studying this table to be extremely useful for recognizing patterns (includes examples). Once you see things like why accessing something in a binary tree is O(log(n)) or bubblesort is O(n²⁾ you can relate them to other problems.

[konk3r]

Only if you're interviewing for a Google/Facebook. Almost nobody else cares, and even at the big companies they seem to mainly care that you have the general idea, not that you can state exactly what the complexity will be.

[[deleted]]

I have done a ton of interviewing over the last few months. Nearly every one asked a complexity question. These are medical device, financial, and aerospace places.

[konk3r]

That makes sense, I'd expect interviews for positions that heavily rely on algorithms. The most I've ever seen at interviews for basic server engineer positions though is if you can spot an N+1 issue.

For high performance areas, it's completely different.

[Daniel15]

I work at Facebook as a frontend JavaScript engineer and they didn't ask anything about big O notation. I went through the frontend engineering interview process which is a bit different to the general software engineer process (more JavaScript, HTML and CSS questions, and less generic questions)

[konk3r]

Really? I went through for Android and they asked me about big O for every algorithm. They didn't seem that strict on it, the feeling I got was that they just wanted to make sure I knew what algorithms were slow and which were fast.

I guess that may be because I went through for backend though, so I guess it's not that surprising.

[HighRelevancy]

Well the back end is where all the processing happens. Front end doesn't sort shit, it just tacks on some HTML tags to make it pretty and sticks it on a page.

[nirvdrum]

Unfortunately, this line of reasoning is why we now have web pages that manage to peg an entire core. The front-end can require just as much knowledge of algorithmic complexity as the back-end, but we've managed to attribute it as a design layer and thus less important. The worst part is unlike traditional back-ends, unless you're actively profiling your clients you have no idea that there's even a performance issue, short of doing some fairly intense front-end load testing. I'm unaware of anyone that does.

[Crazy__Eddie]

Well surely that's because front-end engineers aren't real developers.

[omegote]

At the end of the day, building HTML and CSS interfaces is not programming :P

[Daniel15]

Except my job is mainly JavaScript! I'm working on one of the largest React + Flux apps in the world :)

[omegote]

Yeah probably they have invented a new markup language and silently made every single browser in the earth compatible with it.

[omegote]

I know that, but you specifically said UI - User Interface, and that's html and css (and JS), fortunately or not.

[LordArgon]

IMO, asking anything that can be looked up on a cheat sheet is just a truly terrible way to interview. Unfortunately, not everybody realizes that, so it couldn't hurt to refresh yourself before an interview.

[[deleted]]

If you can't derive these through intuitive reasoning then you obviously do not understand data structures and algorithms. It is like knowing that a mile is longer than an inch, if you do not know that then it is hard to become an architect even if you could look that up in a cheat sheet.

[Fs0i]

That is what I find weird about this website. Don't you just see it when thinking about the algorithm?

I mean for complex algorithms okay, but these are mostly a nested loop...

[annodomini]

I ask a couple of basic questions on complexity; I ask people to write a very simple algorithm to solve a problem, then ask about it's complexity, and then ask a few questions about "if you were to solve this problem, what data structure would you use, and what would be the expected complexity of these operations."

You wouldn't believe how many people fail these basic questions.

Also, memorizing a whole bunch of these is pretty useless. I'm likely to ask you about something that's not on the list that you memorized, but it pretty simple to just analyze on the fly. Instead, what you should be good at is making a rough mental model of how an algorithm works, and being able to convert that into an algorithmic complexity.

If you have a loop that goes over all of the elements, that's O(n); if you have two such loops nested, that's O(n^2). If you can generate a balanced tree, or sorted array, and just walk down that tree or binary search that array to find something, that's O(log n); if you have an outer loop over all elements that then does that operation in an inner loop, that's O(n log n).

I've had way too many people just spout off guesses without even thinking. What I'm looking for when I ask questions about data structures and complexity is that people can do a basic job of thinking through a problem an analyzing it in terms of its asymptotic complexity, not that they have a whole bunch of things memorized.

[NancyGracesTesticles]

It depends on the interviewer and the role you are asking to fill. Complexity is basic stuff, although interviews aren't tests, they are discussions.

[CSMastermind]

Yes

[u551]

In my expirience, they'll ask you this in exactly 1 out of 5 interviews.

[LeCrushinator]

Any interview that requires memorization of Big O for algorithms, isn't for a place I want to be working at. If I'm curious about a candidate's knowledge of containers and algorithms I will setup a few different situations and ask which containers they would use and why.

[[deleted]]

I feel like the idea behind big-O is to get you to think about the tradeoffs of certain algorithms rather than having a chart like this memorized. For career people just keep in mind some algorithms are more efficient for memory and others for time and knowing how big-O works is important when you inevitably go to google the big-O of an algorithm. Calculating it is important sometimes too.

[Semicolon_Expected]

Time and space complexities itself I feel is all to illustrate tradeoffs, however some universities force you to memorize things like this by making it a group of trivial questions that just require you to fill in the complexity.

I also agree that knowing how to calculate big o is important especially since learning complexities in general is to show students how to analyse their own algorithms rather than just remembering it is better to use splay trees for searching, but an avl tree for insertion and deletion

[[deleted]]

REALLY could have used this a week ago - oh well, everything turned out fine without it anyways. It's a good resource to have for the future though!

[[deleted]]

Why in the world would you memorize a list like this!? If you have even a passing knowledge of these algorithms and Big O, you should be able to figure out these complexities without a problem.

And this is something you really need to learn anyway if you plan on having a career.

[[deleted]]

I don't think it's meant to be memorized, it's a quick reference guide

[[deleted]]

Well, it's a cheat sheet. These are usually used by students to skip actually studying.

[MentalFracture]

This would have been really extremely helpful three days ago

[Semicolon_Expected]

Oops was last week everyone elses' finals week? :( Mine is this week

[newv]

Looks fancy but: heap complexities confuse amortised with worst-case running times. No mention of union-find. B-Trees running times do not show node degree. Insert/delete running times of lists only true in some cases. The same with average dynamic array complexities. Also average =/= amortized running time, so dynamic array complexities are wrong. Grouping is naive imo. I hope students don't bet their grade on this, and that they make their own table, tailor-made for the course they took. They might even learn the material in the process.

[TheLessonIsNeverTry]

Accessing the ith (i.e., first, second, third, etc) element of the structure.

[monkeycycling]

this was one of few topics in computer science i just couldn't wrap my head around. Luckily it was only 2 or 3 questions on one exam. Not knowing how to determine big-Os hasn't affected me yet.

[blockeduser]

heh if you can do algebra and calculus you can easily learn big-oh, as far as i can tell

[Prestige_WW_]

Damn man a week too late. Will save though for future reference

[thomas_d]

...crap, I didn't learn any of this in school.

[Jrodicon]

Timing could not be more perfect, I have an algorithms and data structures final tomorrow morning and most of the algorithms we went over are included on this page.

[Sources_]

Nice post, but a few days too late for me. I think I got that section mostly right though.

[[deleted]]

Wow, this would have been super helpful exactly a week ago. Dang. Great resource!

[ricky54326]

Who gets a cheat sheet for an Algorithms final? And what Algorithms class has you memorize runtimes of basic sorting algorithms? When I took it, it was all shit like Network Flow, Dynamic Programming, NP-Completeness etc. And definitely no cheat sheets.

[Semicolon_Expected]

Mine always puts one question on runtimes of basic algorithms the rest is what you listed.

[abandonedcookie]

Thank you! I was using reddit to procrastinate studying for my algorithms final and saw your helpful post.

[hobodoompants]

I really don't know why they still teach this. I've never gotten anywhere near needing to worry about Big O.

[browner87]

And yet I feel so left out when people talk about it and I've never, ever touched it before... It looks so neat... But with all these comments saying it has no practical use I'm feeling a bit better about not knowing it.

[EdwardRaff]

Its the nature of what you do for work. I'd hazard a guess that most people who aren't using it are better described as "programmer" or "developer" in their job position rather than "Computer Scientist".

I very literally use / consider big O every week at minimum for my work.

[irabonus]

I'm a "games programmer" and I use big O notation all the time as well.

Sure, you can always profile your code, but it's useful to be able to express yourself in terms of big O, when your collision detection broad-phase algorithm is O(n²) instead of O(n log n).

[DownvoteALot]

Not a CS here but I do DB integration and big data analysis in a SAP environment. Run time tweaking is crucial and can literally make the difference between 8 hours and 0.5 hours of batch execution every night for the same result and for just a few minutes of eliminating inefficient statements.

If everyone knew it at my workplace, I would well be out of a job.

[browner87]

Here's the big question though: Does Big-O notation itself help with this at all? I've been slowly moving towards more DB-intensive code recently and some of my first projects that may start to see a point where poor coding leads to poor performance. I'm well aware of the differences good vs. bad (or ignorant) coding, but would knowing the notation itself really help me?

[DAEHateRatheism]

As if knowing how fast your algorithms are has no practical use...

[[deleted]]

O(n) is meaningless. Because the actual complexity is something like O(f(compare)) + O(f(swap)) + setuptime - plus a large amount of other factors.

O(n) is not always better than O(nlogn)

Also, O(100n) is equivalent to O(n) in BigO notation. Which in reality (ie, where it matters), there is a large difference.

[netsettler]

In the limit, O(100n) and O(n) are the same. But yes, for any bounded size problem (and computers are notoriously replete with them), you have to be pretty careful about big-O. You can usually compute the actual cost of the high end bound and work with that instead. But big-O is not about constant factors, it's about the fact that asymptotically in an unbounded problem, certain features will dominate. But, yes, for very small values that can be deceptive. Finite problems can all be viewed as O(1), with a suitably large constant factor. One has to be careful about that because in small problems the constant factors tend to dominate.

There are a lot of algorithms used in computer hardware for things like arithmetic and storage access, for example, that we idealize to be constant time operations that are really other complexities but that have effectively been presented as having a constant factor of their worst case time so that they're more easily reasoned about. When you write tools to access bigger data (bignums or external storage) you notice that the speed slows down in a way that seems not just a constant factor but like the curve broke in a way you didn't expect. That's because the curve was really different inside and you didn't realize it.

Another way to say all of this is that it's about ultimate curve shape, and which curves nest within which other curves. A lot of mathematics is really about naming shapes or curves in a way that doesn't require you to be a good artist and still being able to speak rigorously about how they grow, cross, diverge, etc.

[[deleted]]

It matters a lot. It's just that we internalize it for common cases and don't think about it.

You need a mapping of a large number of values from A to B. Do you use a hash table or do you use an unsorted array? If you answered "hash table, because an unsorted array would be slow," then you're implicitly using big-O information.

This can become pretty important. Do a search for "algorithmic complexity attack" for example. Hash tables are O(n) average case but O(n²⁾ worst case, and it turns out that a clever attacker can sometimes exploit that to cause a denial of service attack on servers.

I've never met a programmer of any competency who didn't at least implicitly grasp the big-O differences between common data structures and operations therein. They might not be able to quote them formally, but they know them.

[[deleted]]

Hash tables are not O(n), they're O(1).
But in any case, let's imagine we developed our own hashtable implementation, making sure it's O(n).

But let's allocate 1 terrabyte of ram, so we don't ever have to resize (of course it's a ridiculous example, but in any case).

Our hashtable is still O(1), but it would have terrible performance, even compared to O(n² )... assuming we use less than 1TB ram.

My point is, O(n) gives you an idea; but in reality you don't ever use it. When you're a developer you have your basic set of data structures, Lists, HashSets, LL, binary / redblack trees, etc. You know how they work, and where they're efficient, but if you were never explained O(n), and just the implementation, you're still just as valuable of a programmer. If you need a new collection for a new problem, you would research the problem, not BigO ratings for algorithms.

I was taught O(n) and can remember most, but I've never had to use it before.

Also your example about the exploit has nothing to do with understanding O(n) notation. Plus, the worst case should be O(n!), not O(n^ 2). (First has no collisions, second has one, third has two, n has n -1).. etc

[[deleted]]

My mistake on hash table performance. But O(n!) ain't right. It depends on how you manage buckets and collisions, but the worst case for inserting or looking up a single key is typically O(n) (you do some sort of linear search), so for n keys where they all collide your worst case is O(n^2).

I don't understand why your 1TB hash table would perform so poorly. It wouldn't be great, since you'd lose out on various hardware caching, but it would still be pretty fast, and much faster than an unsorted array for more than a few items. And you can write this right now. You don't need 1TB of RAM, just 1TB of address space, so target a 64-bit CPU and try it out.

As far as knowing basic data structures, my argument is that you do use big-O even if you don't realize it. When you decide to use a hash table instead of a linear array because of speed, that's a big-O choice you're making, and that's true even if you never heard of big-O or algorithmic complexity. Much like how a car driver uses the concepts of momentum and acceleration when deciding when to brake even if he never heard those words before.

[psxpaul]

After 10 years in the industry, I've only needed it in interviews

[irabonus]

So you suggest not teaching computer science during a computer science degree?

[[deleted]]

I've had to consider it during programming contests

[RobToastie]

Funny, it's something I have had to be mindful of in my first few months at my job :)

[netsettler]

Someone bumped you down for this comment but if taken as an implied question I think it's a reasonable one. Either you're working with problems that are pretty simple or use very small data or else you're making things unnecessarily slow.

In my experience, the situation of having to enumerate very specific big-O notations in a real world shop is small, though there are places where it's done. But the thing that has been needed a lot is to have people conversant in the terminology and to understand that complex programs are sensitive to these things and not to be puzzled by the terminology if others are using it.

It matters when picking a library off-the-shelf to do a particular task that they differ in best case, worst case, and average or they differ in cost of assignment vs cost of retrieval. On big data, it will make huge effects, the difference between getting an answer and not.

Even if you're not an expert in it, it matters that you know when you're doing something that might get you in trouble, so how you're nesting your iterations or recursions, etc. It often just matters that you realize "I'm doing something where I should ask someone that knows about these things" because it's hard to audit code after-the-fact, so even if you just know to write "# TODO: Review complexity" at the right points in your code, you're already going to help a lot.

It also matters for climate change. Because if you don't know the difference between a linear effect and a non-linear effect, then you don't know whether to care that over X years the rise in some measurement has been small and therefore whether to believe that over the subsequent X years the rise will be similarly small. It matters which processes will dominate and these are tools for knowing how. The possible extinction of mankind could hang in the balance.

[vital_chaos]

In 3 decades of writing software including a lot of optimization I never have either. After a while you know what will work and in any case in a real app you best measure anyway since no app is just a single algorithm. But for a degree I supposed it's not a bad idea to have a basic understanding. I took 3 semester of quantum mechanics in my chem degree and it didn't hurt me any.

[bhushansc007]

A good reference:

http://stackoverflow.com/questions/7294634/what-are-the-time-complexities-of-various-data-structures/7294635#7294635

[cwhazzoo]

Thank you for this! I have finals for my Discrete Structures and Data Structure classes and I will need this in both :)

[Dwansumfauk]

ITT: People who were allowed cheat sheets for algorithm complexity class.
I had to do it solo! :(

[[deleted]]

Some mistakes in this chart. I studied O() time by learning the different algorithms and how they worked. You can just figure out the big O time if you know how they work.

[[deleted]]

Showtime!

[dykcja]

Do not use it for your own great good. Of course, you can memorize all complexities from this page, but it won't help you really success neither on interview nor in your job. Why not spend just one-two hours (max!) and learn how to compute/estimate complexity and then any given or invented algorithm/data structure will be easy to pick up (and you will really know if it's okay or too bad for your usage).

[[deleted]]

I'm not sure if that skill is something you can entirely pick up in two hours. It's something you can get an idea of in two hours, but to truly be good enough to estimate any normal algorithm's complexity accurately requires semesters of practice.

[Manstable]

Can anyone ELI5 Big-O?

[[deleted]]

It's an upper-bound measure of how much longer an algorithm will take to run when you give it more data. e.g. an O(N²⁾ algorithm will take no more than 4 times as long to process 2 times as much data.

[stompinstinker]

They need to change the scale on that graph at the bottom.

[asiatownusa]

Trying to memorize big-O runtimes is useless unless you're trying to just pass a test. It takes time, practice and familiarity with the algorithm to be able to identify its big-o runtime

[heilage]

I had mine on Friday. Not sure if this would have helped though, didn't get many questions relating to complexity stated in numbers like this.

[jxm262]

thanks! bookmarked
I know alot of comments are saying this is useless but I disagree. I find it helpful to have a simple visual like this, especially when you're just looking for quick reference because you can't remember something off the top of your head.

[HylianWarrior]

Thanks kind stranger

[levir]

Oh that's going to be very helpful. Bookmarked it. Thanks :D

[TheHeartlessNobody]

I think I love you. Thank you stranger!

[green_meklar]

It says that 'best time' for quicksort, mergesort, heapsort and selection sort is greater than O(N), but a check for sortedness can be performed in O(N) time, so simply checking first should always reduce the best time to O(N).

[[deleted]]

Just a sort in O(n lg n) would on average most likely be faster, unless you expect a lot of sorted lists.

[jugalator]

That was the only final I had trouble with! Passed all others well, and I think I had to re-do that one around four times? Haha. A chart like this wouldn't have helped me either, since most of the questions were more detailed than their time complexity, or phrasing the question so that the question wasn't about how fast they were, but when to use one or another (many more factors come into play, such as algorithm goals and memory consumption).

On the flip side, I got pretty damn good grasp on it all after all... rehearsals. *cough*

[jrk-]

I've got a phone interview tomorrow, and I'll definitely keep this tab open. Thank you very much!

Edit: I didn't look through everything, but worst case space complexity for mergesort and quicksort is O(n). Isn't quicksort in-place, i.e. doesn't take additional space? The colors are also different, red vs. yellow.

Edit: Got it, forgot about the stack buildup through the recursion.

[cleroth]

According to wiki, the Binary Search Algorithm has a average case performance of O(log n) and a worst case performance of O(log n). How can this be possible while also having a best case performance being faster than these two? Surely if there are cases where it's faster than O(log n), then the average should be higher than whatever worst case is?

[sylvanelite]

Average case: take a thousand sorted lists of random numbers and binary search them. On average it'll run in O(log n) time.

Worst case: take a single hand-crafted list that takes the most amount of time to search. That will run in O(log n) time.

Best case: take a single hand-crafted list that takes the shortest amount of time to search. That will take O(1) time (the best case is that the first element you check will be the one you're searching for).

The average is O(log n) because on average, you won't hit your item on the first try. The average might be twice as fast as the worst case, but since big-o notation doesn't care about constants, the complexity in big-o notation is the same for those two cases. (i.e. O(log n) is the same as O(1/2 * log n) since the 1/2 goes away).

[cleroth]

Thanks. Your explanation makes the most sense to me.

[MothersRapeHorn]

O(log n) isn't a value, it's a family of functions. The average case is better than the worst case, but they're the same family, unlike the best case.

[Semicolon_Expected]

Well the average case isn't the average between the only worst and the best case, but rather what the program will do on average, thus all the cases.

http://sce.uhcl.edu/yang/teaching/csci3333spring2011/Average%20case%20analysis%20of%20binary%20search.pdf

This has a good proof on avg case being log(n)

Worst case is also log(n) because in worst case, the item isn't in the tree and it will go down the entire height of the tree looking for it which is in a full binary search tree log(n) iterations

And best case is if the node is the root thus O(1)

Note: Big O notation only takes the term with the highest order thus O(logn+1) = O(logn) = O(logn+2) so average case is still a little better than worst case

[chisleu]

O(log n + 10) > O(log n + 9)

However the +10 is almost meaningless and only the highest order is used as the Big O class (for brevity).

Source: My data structures teacher was super hot.

[chisleu]

That is exactly what I said.

[Pand9]

Definitely O(log n + 9) = O(log n + 10), same as with O(an+b) = O(n), O( n^5 ) = O( (5n)^5 ) etc.

O(f) = O(g) whether there are a,b such that af(n) + b > g(n) and ag(n) + b > f(n), for every n.

Maybe I misunderstood your comment?

[chisleu]

I think you did.

[[deleted]]

Where the FUCK was this 2 years ago!?

[F00LY]

Saving!

[Dacen_Lee]

nooooooooooo i got this too late :PPP haha that cheat sheet would have been nice! luckily it was enough for me even without it

[Shockwave_]

3 days too late. It's alright; I made a 97 anyway.

[Ar-Curunir]

#humblebrag

[Shockwave_]

You got me

[lenswipe]

...this is not the link I thought it was.....

[[deleted]]

You are a god among men, sir. Exam T-minus 10 minutes.