DEV Community

Cover image for Big-O Cheat Sheet
Ben Lovy
Ben Lovy

Posted on

Big-O Cheat Sheet

A classmate in my Data Structures & Algorithms course this semester posted this link, created by @ericrowell. I'd never seen it and it instantly ended up in my bookmarks, so I wanted to pass it on:

Big-O Cheat Sheet

It provides a table that gives Big-Θ and Big-O complexities for a set of common operations on range of data structures, as well Big-Ω, Big-Θ, and Big-O for various array sorting algorithms.

I'm thinking about buying the poster...

poster image

Top comments (17)

Collapse
 
rumkin profile image
Paul Rumkin • Edited

I've published a paper (Big O of Intelligence) about algorithm complexity of human-involved algorithms. Hope it would be useful for software architects.

Collapse
 
aleksandrhovhannisyan profile image
Aleksandr Hovhannisyan • Edited

I generally don't recommend using one of these and/or memorizing the Big-O performance of algorithms. If you find yourself doing that, then you don't understand what the algorithms are actually doing, and that's a more fundamental issue that you should address.

When interviewers ask you to state the Big-O performance of an algorithm, they don't do it to see if you know the Big-O notations of algorithms, per se. They test to see if you understand how the algorithm performs. And if you know your algorithms, then that should be a (relatively) easy question to answer.

Fun fact: I've never had an interview where someone asked me about any of these CS algorithms/data structures. More often than not, you are asked to write a solution to a particular problem and then assess its performance. That is something you can't memorize, but certainly something you can 1) understand, and 2) practice.

Collapse
 
deciduously profile image
Ben Lovy • Edited

This is a good point, of course rote memorization will not replace actual understanding, and one would hope any decent interviewer would be able to instantly tell the difference. I don't think the point of charts like these is to cheat at interviews.

That said:

I've never had an interview where someone asked me about any of these CS algorithms/data structures.

This likely varies by job domain/region/experience/whatever - I've only had one interview where I wasn't asked some arbitrary academic question about a data structure I'd never need to know in practice. Technical interviews are pretty varied, and usually broken, but this sort of thing has definitely been a theme for me. Usually in the context of a challenge problem, like you said, but I've been asked to cough up and compare and contrast options to fit a problem. A huge theme of my interview experience is "okay, tell me what the Big-O of your current solution is, and then improve it given the data is constrained by whatever". Studying a chart like this helps me, at least, even though I do understand conceptually why the values are what they are.

Collapse
 
aleksandrhovhannisyan profile image
Aleksandr Hovhannisyan

and usually broken

You can say that again.

I once had a phone screen where I was asked to estimate how many feathers would fit inside the volume of your typical brick.

That was my biggest WTF interview to date.

Fortunately, my other interviews have been pretty pleasant (so far).

Thread Thread
 
deciduously profile image
Ben Lovy

So, yeah, I agree, that's ridiculous. I do sorta see what they're getting at though - they want to hear you talk it through. My similar example is "how many gas stations are there in the Continental US?". Who knows or cares about the answer, but a dev employer would care about how you approach the problem.

Collapse
 
drayilara profile image
Ayilara Sodiq

Its 2022,and your approach is still valid.I bet it will still be valid in 2040.

Collapse
 
markoshiva profile image
Marko Shiva

Thats bonkers. :)

Collapse
 
kriska profile image
Kristina Gocheva

Haha, that reminds me of the time I did by hand something similar in my notebook for my DSA course. Surely it looks neat. Personally, I would prefer it wasn't on a black background. It would have been so much easier to read 😄 But I am one of those people whose IDE is not black so perhaps that why 😄

Collapse
 
gabbersepp profile image
Josef Biehler

This is one of the most valuable topic I encountered during my study.

Collapse
 
awoimbee profile image
Arthur Woimbée

This is why I don't like big-O.
Unless you are in O(n2) or more territory, the implementation is a lot more important than the complexity.

Collapse
 
gypsydave5 profile image
David Wickes • Edited

OH!

Collapse
 
mehdishahdoost profile image
Mehdi Shahdoost

A funny tweet but practical way to remember Big O notation :).

Collapse
 
rishitkhandelwal profile image
Rishit Khandelwal

my usual big-O score:
O(n3!)

Collapse
 
koryteg profile image
Kory Tegman

awesome work.

this topic is so confusing at first and this is a great way to simplify it.

Collapse
 
deciduously profile image
Ben Lovy

All credit to @ericrowell!

Collapse
 
markoshiva profile image
Marko Shiva

Thanks for that cheat-sheet.