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

## An introduction to time complexity with help from Ratatouille

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!

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.

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!

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, c*onstants 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! 😰

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!

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