5 Steps to Crushing Big O

Understanding why Big O notation is important and how to calculate it

Image for post
Image for post
Image from: Bae S. (2019) Big-O Notation. In: JavaScript Data Structures and Algorithms. Apress, Berkeley, CA.

Why we use Big O

Imagine asking ten developers to come up with a function that performs a certain task. They all create functions that work perfectly, but how many do you imagine are identical in code? Probably none, especially if the task is moderately complex. So how do you know which function will be the most efficient? Could it be the developer that wrote their function in three lines of code? But what if they have computer from 2006 and have spotty wifi? Will their function run faster than the 20 lines of code on a 2020 laptop?

General concepts

When it comes to figuring out the Big O of an algorithm, it takes some practice but can be easily mastered with the following five steps.

Step #1: Count the steps

Let’s take a look at the code below. Would there be a runtime difference if items_array contained 5 elements vs 10000000 elements?

Image for post
Image for post
Example taken from Interview Cake’s Big O Notation and Space Complexity. Click here to view.
Image for post
Image for post
Image for post
Image for post
Image for post
Image for post
Graph showing the various types of algebraic runtimes in Big O. This is not all of the possible runtimes, just the most common.
Image for post
Image for post
Example of O(n²) runtime with nested loops

Step #2: Different steps get added

Ok, so we’ve had a quick introduction into loops, but what about algorithms that have more than one thing going on? Great question! One important thing to remember about Big O is that n has to mean something. If you are dealing with more than one something, then you are going to need more than one variable. Also, n is just a common practice variable but we can easily describe all of the functions we’ve seen so far as something else, like O(4), O(a), O(b²), etc.

Image for post
Image for post
Example of a function where the variables are added for Big O

Step#3: Drop constants and coefficients

Yup, you read that right! When it comes to Big O, we don’t care about constants or coefficients because what we are really after is how the function scales.

Image for post
Image for post

Step#4: Drop non-dominant terms

Ok, so this one seems a little tricky and counter intuitive but stay with me. Let’s say we have an algorithm we’ve calculated as O(n² + 4n³), how can we pare this down?

Image for post
Image for post
Pseudocode illustrating how dominant and non-dominant terms change as N gets larger

Step #5: Different inputs get different variables

Finally, when dealing with multiple inputs, we must remember to use multiple variables. After all, n in O(n) is a data input, not just a random letter someone decided to stick between parenthesis. If we have multiple data inputs then they each must have their own unique variable to acknowledge their relationship.

Image for post
Image for post

Conclusion

Big O can be tricky and, frankly, I am still on my way to really understanding this concept. There are a host of resources and tutorials out there in the world and I highly recommend you comb through them to get a better grasp of what is going on with Big O. I didn’t even touch on a handful of common runtimes, such as O(x!), O(x log x), or O(log x), but I highly recommend reading more about them as they will likely pop up in any leetcode data structure questions or even technical interviews. If I figure out what they mean, perhaps there will be a sequel to this post…

Resources

Below are some of the resources I found helpful in tackling the basics of Big O notation.

Software Engineer, volleyball player, lover of tiny houses and all things spicy.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store