A Beginner’s Guide to Big O Notation (Part 1)

An introduction to time complexity with help from Ratatouille

Alison Quaglia
Sep 14 · 6 min read

When we write code, it’s important to understand how our choice of code impacts the speed and performance of the program we’re creating. Big O Notation is a way to classify how quickly the runtime of the algorithm/number of operations or space increases in relation to the input n. It looks at the worst case scenario, assuming every possible element is touched on as the algorithm is written.

There are seven classifications in Big O Notation, ranging from fantastic, fast and/or space efficient solutions that remain constant despite the input size, to absolutely terrible, please-don’t-ever-use-these solutions!

big o complexity chart
big o complexity chart

Understanding how different data structures and algorithms fit into this Big O complexity gradient can help you select the right ones and optimize your code at work — or for a tech coding interview, perhaps.

O(1) Constant Time

Let’s say that you’re Chef Remy and you’ve been asked to cook your world famous Ratatouille.

chef Remy cooking ratatouille
chef Remy cooking ratatouille
Yum! Image credit: Pixar

The first thing you do is gather the ingredients, spices and herbs to prepare the dish. The kitchen is your second home — you know exactly where to find everything you need:

let kitchen = {
vegetables: {
broccoli: {name: "broccoli", ...},
zucchini: {name: "zucchini", ...},
eggplant: {name: "eggplant", ...},
carrot: {name: "carrot", ...},
squash: {name: "squash", ...},
tomato: {name: "tomato", ...},
radish: {name: "radish", ...},
cabbage: {name: "cabbage", ...},
redPepper: {name: "redPepper", ...}
},
seasoning: {
onion: {name: "onion", ...},
garlic: {name: "garlic", ...},
basil: {name: "basil", ...},
oregano: {name: "oregano", ...},
herbesDeProvence: {name: "herbesDeProvence", ...},
sage: {name: "sage", ...},
ginger: {name: "ginger", ...}
}
}

You don’t need everything in the kitchen for this recipe — broccoli and ginger don’t belong in ratatouille after all!️ Instead, you grab only the ingredients you need, like this:

let ingredients = []ingredients.push(kitchen.vegetables.zucchini.name)
ingredients.push(kitchen.vegetables.eggplant.name)
ingredients.push(kitchen.vegetables.squash.name)
ingredients.push(kitchen.vegetables.tomato.name)
ingredients.push(kitchen.vegetables.redPepper.name)
ingredients.push(kitchen.seasoning.onion.name)
ingredients.push(kitchen.seasoning.garlic.name)
ingredients.push(kitchen.seasoning.herbesDeProvence.name)
// ingredients = ["zucchini", "eggplant", "squash", "tomato", "redPepper", "onion", "garlic", "herbesDeProvence"]

What would the Big O notation time complexity of those operations be? 🤔

Each of these operations (grabbing the ingredient, pushing it into the ingredients array) takes constant time, or O(1). The number of operations doesn’t grow with the size of the array or the size of the kitchen object. We have direct access to each element to grab exactly what we need, so the time complexity does not change.

Here’s another example:

function addDigitsUpToNumber(n) {
return n * (n + 1) / 2
}
addDigitsUpToNumber(5) // 15, same as 1 + 2 + 3 + 5 = 15

In this function, we add up all of the digits, from 1 to n, and return the sum by using a quick math trick. This function also has O(1) time complexity because it takes the exact same number of operations regardless of whether n is equal to 5, 10, 1,000 or 1,000,000,000.

O(n) Linear Time

To start preparing ratatouille, you first have to chop the ingredients:

let ingredients = ["zucchini", "eggplant", "squash", "tomato", "redPepper", "onion", "garlic", "herbesDeProvence"]function makeRatatouille(ingredients) {
function chop() {
for (let i = 0; i < ingredients.length; i++) {
console.log(`${ingredients[i]} has been chopped!`)
}
}
}

How long should our makeRatatouille function take to complete? Better yet, how many operations need to take place? 🤔

Since there are seven elements in our ingredients array and the function iterates through each one once (chopping as we go), we could say that seven operations need to take place (O(7)). If we added additional n ingredients to our array, this function would take n operations since it needs to touch upon each one of those elements once, otherwise known as O(n).

O(n) time complexity is also known as linear time and is generally considered an efficient solution. It isn’t as good or as fast as O(1) or O(log n), which we’ll get to later, but usually this time complexity is considered acceptable.

What would happen if we added another iteration? After all, those ratatouille ingredients need to roast in the oven!

chef Remy prepping the ratatouille for roasting
chef Remy prepping the ratatouille for roasting
Image credit: Pixar
let ingredients = ["zucchini", "eggplant", "squash", "tomato", "red pepper", "onion", "garlic"]function makeRatatouille(ingredients) {
function chop() {
for (let i = 0; i < ingredients.length; i++) {
console.log(`${ingredients[i]} has been chopped!`)
}
}
function roast() {
for (let i = 0; i < ingredients.length; i++) {
console.log(`${ingredients[i]} has been roasted!`)
}
}
}

Our makeRatatouille function now needs to iterate through all of the ingredients twice: First, in the chop function, then again in the roast function. We could say this function takes O(2n) time, since it will iterate through the ingredients array exactly twice.

The time complexity of this function still grows in proportion to n, so we would remove any constants (the number 2 in this case) and call this O(n), just as before. Even if this function had additional operations that came out to O(4n + 20), for example, we would still shorten this to say O(n), because in Big O notation, constants and smaller operations aren’t counted.

O(n²) Quadratic Time

As Chef Remy, you hear that famed restaurant critic (and notorious grump) Anton Ego is coming to judge your food for the first time. Yikes! 😰

anton ego gif
anton ego gif
Image credit: Pixar

He will accept only the best, so you decide to sort through all your chopped vegetables to find the best ones for his ratatouille. Let’s pretend that each slice has a rating from 1–n, with 1 being the best slice and n being the worst:

let zucchiniSlices = [20, 11, 25, 3, 14, 5,...]function sortByBestSlices(veggieSlices) {
for (let i = 0; i < veggieSlices.length; i++) {
for (let j = 0; j < veggieSlices.length; j++) {
if (veggieSlices[i] < veggieSlices[j]) {
let temp = veggieSlices[i];
veggieSlices[i] = veggieSlices[j];
veggieSlices[j] = temp;
}
}
}
return veggieSlices
}
sortByBestSlices(zucchiniSlices)

The time complexity for this function is pretty bad. Here we’re looking at O(n²), also known as quadratic time because we have a nested for loop situation. In this function we are iterating through each slice in our veggieSlices array, comparing it to all other slices one by one, as n * n. If the array had 30 slices, we would have 30 x 30 operations (900). If we had 100 slices, to sort them this way would take 10,000 operations!

The runtime could grow pretty fast — and Anton Ego is waiting for his meal! Isn’t there a more efficient way to sort, that has less impact on the runtime?

Of course there is!

There are many algorithms that are much faster than O(n²), such as those that run in O(log n) and O(n log n) time. We’re going to explore those in Part 2 of this series.

In the meantime let’s pour another glass of wine for Anton Ego and hope he stays patient. 🍷 Stay tuned!

anton ego waiting gif
anton ego waiting gif
Image credit: Pixar

Update: Check out part 2 where we dive into O(log n), O(n log n), O(2^n) and O(n!) here!

Better Programming

Advice for programmers.

Alison Quaglia

Written by

Apprentice Engineer @ Pinterest. Bridging the gap between development and design. A believer in kindness above all things. 🌱

Better Programming

Advice for programmers.

Alison Quaglia

Written by

Apprentice Engineer @ Pinterest. Bridging the gap between development and design. A believer in kindness above all things. 🌱

Better Programming

Advice for programmers.

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

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