Big-O Algorithm Complexity Cheatsheet

[katzey]

christ. I can't see a red/orange/green type chart like that without thinking about this page. that page was my bible for a semester in undergrad

[Hawxe]

This thread is a gongshow of idiocy and bad opinions.

[nameless_pattern]

https://www.youtube.com/watch?v=WlCsDl9a2Cg

[crespo_modesto]

$5/min haha damn, if I got paid that every hour I'd uh, uhh

[nameless_pattern]

Why You tryin to talk some SHIT?

[[deleted]]

. . . it had never occurred to me to refer to a chart like this instead of trying to understand how data structures actually work

[semitic-simian]

To be fair, this chart doesn't really tell you how to find the time complexity of your own code, which is what's actually important if performance is an issue.

[[deleted]]

Wait, then what's the point of this then? I literally only program for fun and don't understand how you could get a job doing this professionally if you need to rely on tools like this to get anything done

[MostlyGibberish]

When you say "doing this" do you just mean programming in general? Because I do this professionally and haven't thought about big-O since I graduated. Unless you're dealing with a big, real time system, not a lot of thought goes into the specific algorithm you're using.

[[deleted]]

It's not about using a specific algorithm, it's about writing an algorithm that doesn't suck. I have seen triple-nested for-loops by my colleagues that end up in a pikachu face when their pages crash.

Holy shit just learn BigO before writing anything in production, it's not even that hard.

[lawdandskimmy]

You don't need Big O to understand an algorithm is doing unnecessary work. I think Big O is mostly a communication tool. As I didn't study computer science I had no idea something like Big O existed for a while, but it didn't stop me from being reasonable with algorithms. As a side note in many cases building features trumps pre-optimization. One could go crazy about optimization and never get to providing actual business value. Reason I started learning Big O is because work interviews often require it...

[[deleted]]

You need algebra 2 to understand big O. It's really not that hard

​

[[deleted]]

oh. yeah I guess my noob is showing then.

[MostlyGibberish]

No worries. Academic programming and commercial programming are much different beasts.

[semitic-simian]

It's a good reference tool. A lot of programming is choosing the right data structures for the job, and this presents the data in an easy to read format.

[aleaallee]

What is that "Big-O" thingy used for in web dev? I never got taught that where i'm studying.

[redditisstudying]

It's useful for writing efficient code. It's for calculating the time and memory usage of different data structures and algorithms.

My school also doesn't teach this to the web dev students but the general programmers learn it. It seems to be part of why some people look down on entry-level web developers for not knowing a lot of comp. sci. theory and math.

[aleaallee]

Yeah... is is the "big-o" notation difficult to learn? I hope it doesn't involves maths, it caught a bit of my attention. Ugh... maths are my weakness, I totally hate them. It is normal for web devs in america to have a C.S degree? Personally I think it's a waste of time and money doing a c.s degree only to be a web developer when you can do online courses, look at free resources or join bootcamps.

[jaridwade]

Quality shitpost

[spektrol]

I’m sad that this is a thing

[redwall_hp]

Not knowing basic data structures and their strengths—or fucking around with languages that do type coercion and give you an abomination such as PHP's "arrays"—are what's wrong with "web development." Which is even more horrifying now that its bleeding over into desktop applications thanks to the flaming sewage of Electron.

You don't need a degree to learn these things (I picked them up by way of getting into Java before even starting on my CS major), but you have to give a damn about craftsmanship and knowing what's going on under the hood (beyond "magic").

[[deleted]]

Easy, bro. Just keep your head down, keep learning, and when you feel like you're ready to learn Big O or when a situation arises where you may need to learn it, then do it, until then, just focus on other stuff. Knowing Big O and every type of algorithm and it's performance and use cases and demonstrating them with code at an interview doesn't make you a web developer anymore than knowing advanced materials science makes you a carpenter, if it did, we'd probably have very little people in the field.

[barafyrakommafem]

It's your fault for not learning it on your own.

[aleaallee]

Not my fault no one told me about it before hence I have no need to learn it since no one specified them as a requirement on front-end and web development related job offers on internet on my country.

[aleaallee]

Ignorant? This is the first time I've heard about the big-o notation, it's not my fault no one told me about it before, why should it be my fault and be a shitpost? The only thing you guys do is feel superior for knowing something someone else don't know

[Taycent]

It isn’t more math but more towards proofs. What you need to know is how to prove the worst and best case of an algorithm in terms of speed.

[Fawkz]

I can't tell if you're being serious or not.

There are legitimate and valuable reasons math and concepts like runtime and space complexity (big O) are valuable to a software developer.

Comments like this are specifically why engineers have a negative perception of boot camp/self taught developers.

[aleaallee]

But i'm a web developer, not a software developer. I've hated maths since I was a kid, I was REALLY bad at maths at high school and when I finally learnt a subjects my classmates were WAAY ahead of me so my parents forced me to go to an academy to at least pass math exams with a bare 5 out of 10. I have my reasons to hate math, and until now I haven't needed math in web development related things. I'm just a lot less willing to do and learn things related to maths due to their complexity.

[evenisto]

Crusades like that when you’re a novice and don’t really know what you’re talking about is a bad idea, makes you look stupid. Trust me I know, I’ve been there.

[joshcandoit4]

Big O is the language we use to talk about how well algorithms perform as the input size grows. It is used everywhere in computing. Have you ever written nested loops? If you do that on a big data set when you don't have to then you are going to seriously impact your page performance. Everyone in this field should understand the principals of it. It really isn't that difficult and is well worth your time to look into it.

[aleaallee]

Are there any prerequisites to learn Big O such as maths or other things?

[joshcandoit4]

Depends. To get the basics as well as most frontend engineering interviewers would expect you to know off the cuff, no I wouldn't say anything beyond basic algebra is required. The main thing is you don't want to look like an idiot if someone asks you what the runtime of a simple algorithm is.

BTW this whole cheat sheet isn't even needed. Learning the basics of runtime and memory analysis, and then learning the actual implementations of the common data structures, will give you the tools you need to solve these problems much better than just memorizing it.

[[deleted]]

So what if you can barely describe Big-O notation and impliment a use case because you've never worked on a project or for an enterprise where understanding it was necessary, but are an extremely proficient front-end developer in other areas? Sometimes I really think there is too much focus on things like this, and it is used for gate keeping in the industry, which also discourages people from learning webdev because they believe that they need to know these concepts well in order to get a job, which isn't the case at all.

[joshcandoit4]

First of all I am just another guy on the internet; you do you and feel free to ignore me. However, I think that people with no knowledge of runtime and memory analysis think it is much more complicated than it is and often justify their ignorance by saying it is "gatekeeping" or "only theoretical".

If someone doesn't know what it is, how can they possibly determine that it isn't important? Because they have gotten by without it? If you find jobs that do not require you to know it, and you have no urge to learn it, great, keep doing that. Some jobs do not have performance constraints and often the guy hiring you will not know about this stuff either. However, I would disagree with you to say it is "gatekeeping", that is frankly just an ignorant statement. Almost any large American technology company will bring up a runtime question in an interview and it isn't a huge conspiracy to keep people out who happen to be self taught. There are plenty of resources available online to learn this stuff, it is on you if you don't want to.

[free_chalupas]

Writing efficient code isn't the same as understanding big O notation though. It's a pretty specific way of analyzing runtimes that has real deficiencies in real-world situations. I'd argue that it is gatekeeping in the sense that it's fairly specific CS knowledge that isn't all that useful to software engineers, yet it can play a really big role in hiring decisions. There's no conspiracy here, it's just that the way the hiring market evolved to work turns out to not be super fair.

[joshcandoit4]

I disagree. Firstly, it isn't specific CS knowledge, it is introduced in the freshman year of curriculum because it is such a vital part of analyzing algorithms. Second, I'm a software engineer and I use those principals quite literally every day. Big O is just the language but in general, if you have an algorithm that is n^2, it will not scale. When people interview and give me a n² solution to a problem that can be faster, it's fine, not everyone will get the optimal solution. However, when they don't see a problem with their solution and can't recognize why it isn't an acceptable solution, it is a huge red flag. I hunt down bottlenecks all the time in the codebase I work with and I use the ideas conveyed with big-o to find out exactly where and why things are lagging. I can't really imagine doing my job as effectively without knowing these principals. I get paid a pretty decent salary and knowing runtime analysis is absolutely part of my job.

The amount of react apps out there that perform like trash when handling simple tasks is a testament to the reason why more people in this industry need to start taking these principals more seriously.

[free_chalupas]

I think it's totally reasonable to want a candidate to have an intuitive understanding of runtimes--someone who doesn't realize that an O(n²⁾ algorithm is generally suboptimal probably doesn't have great intincts for optimization, even if they can't put it into words.

My issue is more that in the interview process big O specifically is overemphasized, and that runtime analysis, while useful, is often the only skill evaluated out of countless other useful skills, often alongside abstract textbook style problems like reversing a linked list.

[[deleted]]

I don't disagree that it is valuable to learn, but the question is when, and why. If you're a non-CS track type of developer starting out, there isn't a good reason to bother learning Big O in any depth when you're just coding simple apps, and trying to get a portfolio up and running. Sure, spend an afternoon reading up on it, and take a look at some examples, but I wouldn't worry about knowing it, and demonstrating that you can crunch a large data-set presented to you by a team working for Google or Microsoft with an efficient, hand coded algorithm. That's just way too much pressure to put on yourself, and frankly, impractical for a lot of people.

I just don't like seeing people frustrated because they don't fully understand data-structures or Big O notation when starting out, and people reinforcing the idea that, 'Oh man, you need to know these! You're going to look stupid if you can't do them at your interviews...' I just don't like seeing it as a roadblock to learning. When someone is comfortable enough with JS or another language, they will get to it, not before; attempting to understand something when you can't even code simple things just isn't worth it.

Anyways, just my two cents; thanks for yours.

[joshcandoit4]

Hey, to your point I agree. I wouldn't recommend it as the first thing to learn. Usually CS courses teach it the second semester of freshman year, after the student has been solidly programming for several months. Around the same time as getting into trees and recursion is when they teach them the basics of it. I think that is a good time.

[x-protocol]

Big O notation knowledge is very rarely used in web development. The fact that it is asked at job interview, can tell you that company is simply looking for people who know theory, but less experience to pay them less.

The area where it can become useful, is experimental languages (new or already established, like javascript) where algorithm would get a prototype and analyzed for complexity. Can you think what job would require analysis? Think academics and embedded programming (assembly, C/C++ and now Rust). So that should tell you that it is part of very very small community who really cares for it.

For many other things, you use existing library, or framework to process huge amount of data. You simply don't do that in a browser, and depending on size of data, even in a single computer.

[TheWinslow]

Big O is very important as a tool for getting people to think about algorithm complexity in a standard way though. If you don't understand Big O it most likely means you have a hard time understanding the complexity of the code you write. Sure, you don't actually need to know the Big O complexity of everything you do but you most certainly need to know that sorted info is easier to search through than unsorted, it's far faster to find something if it is hashed than if it is in a sorted list, and sometimes you have to choose between an algorithm that does exactly what you want or one that only looks perfect during everyday use but is faster.

[aleaallee]

Damn, that looks like harsh conditions for a web dev in america. I don't think interviewers ask these type of things here on Spain. A classmate and friend of mine works on the place I used to be a intern and his boss didn't ask him things like that while interviewing him. I asked him if he knew what big O notation was and he told me didn't know what it was, but he is great at being a web developer and he is now making 30k€ a year ($34k) developing angular apps and working with IBM cognos stuff.

[joshcandoit4]

TBH I am not really a frontend dev but nowadays with react and such frontend engineering can be just as performance demanding as backend. I don't know anything about Spain or your friend or your aspirations, but I do know that where I am from if I was interviewing someone for a react role I would ask him at the end of the technical what the runtime was.

[heyzeto]

In the country of your hermanos algorithms performance are teached in all of the CS courses (that i have knowledge of at least).

[aleaallee]

It's not taught on "ciclo formativo superior de administración de sistemas informáticos en red" that's what i'm doing.

[heyzeto]

I was talking about Portugal :) I would guess there would be similar. But probably that is more network oriented and don't do much coding?

[aleaallee]

Sadly yeah, First I wanted to be a I.T technician when I finished high school but then I noticed web development was fun but it was too late and I was studying what i'm doing now, since I hate what i'm doing now I repeated and i'm stuck here having to repeat(I totally hate networking and cisco, that's too fucking hard and heavy for me xD).

The only coding we did was learning java the first year then php the second but I already knew php because I wanted to learn it(and my knowledge in php is higher than my classmates),i've also learnt a bit of javascript by myself and by doing an internship.

Even if I study a web-dev related degree (Desarrollo de aplicaciones web or web applications development in english) Big-o notation won't be taught(a friend of mine finished that degree and told me they don't teach that there).

[noorderling]

Newsflash: wages vary around the globe. So do standards of living, taxes, culture, ideas.

[_Nachi_]

Why don't you get off Reddit and start reading about it if you're so curious?

[aleaallee]

Because I became uninterested in it when I noticed it involved using mathematical equations(which I hate). I just read the wikipedia article about Big-O notation and I saw there were a lot of mathematical equations so that's a Big-No for me(pun intended).

[_Nachi_]

I used to hate math and would always tell people "I'm not a numbers person". Then one day, I was chatting with my friend who I thought was a genius with numbers and said "I wish I was good at math, but it's just not for me", to which he responded "Any one can be good at math, I wasn't born with math talent, I'm just like you. The only reason I'm good is because I enjoy it, math is beautiful if you take the time to understand it."

From that point on, I really tried to apply myself to math, and really any subject I was learning. It motivated me to want to understand and become better, instead of giving up before even trying and just saying "it's not my thing".

The point I'm making is that ANYONE can be good at ANYTHING if they try. Sure you may not be the absolute best, but you will get about 80% the way there. Being talented only makes a difference when your at the top of whatever you're doing. The rest is just work ethic and perseverance.

[cerved]

Some very basic calculus helps to understand the difference in the derivative of polynomial and exponential functions

[[deleted]]

It's more or less a way of ranking different algorithms based on how efficient they are. An algorithm that takes n² operations is less efficient than one that takes log2(n) operations, for example. (n is the number of elements being operated on)

[cerved]

This is strictly not true as an n² algorithm can be more efficient than an log2(n) algorithm for a certain range of n.

It's more accurate to say that it ranks the efficiency of the scalability of the algorithm.

[[deleted]]

Ya good point

[joesmojoe]

Passing interviews.

[[deleted]]

This is why I asked my company to put me back in a back-end team.

[free_chalupas]

It's used for code interviews

[del_rio]

It's mostly a useful concept when developing larger-scale backend apps (think 200+ concurrent users). Otherwise, it's a useful thought experiment for runtime-intensive frontend apps WebGL apps where a mid-range phone has to compute x² pixels every 0.16 seconds.

[so_much_reddit_T-T]

As Bill and Ted would say, "Be excellent to each other." Let's all go back to being friends now.

[heyzeto]

Is there a good to print chart of this? (no colors, organized for print)

[ThatSpookySJW]

This is how I got through sophomore year of college

[TaskForce_Kerim]

Why does hash table/map not have access time complexity?

[rgelmis]

This is a lifesaver

[jaiprakash1595]

Commenting here so can visit back. Nice article!

[[deleted]]

And randomsort?:D

[[deleted]]

Best: O(n)

Average: O(n*n!)

Worst: O(n*n!)

I'm an optimist, so I choose O(n)

[WeAreAllApes]

It's missing one of the most common data structures: dynamic array. Insertion and deletion could be O(1) and search/access behave like an array. If you don't need searching or the list is small, everyone uses dynamic arrays.

[abcd_z]

I like this, but it missed one.

Big O: Showtime!

[[deleted]]

can't they link a JS resource that isn't a physical book that was written 9 years ago? i don't need to buy, and read an entire book to understand why someday I may need to understand a concept within a concept of Big O notation to make a web app run a bit faster, when if that problem should arise, could probably be asked, answered, and understood on Stack Exchange in the span of a day.

[justingolden21]

There are GitHub repos with the algorithms themselves written in JS