Getting to Know the Big O

A very basic intro to Big O Notation.

If you’re in the business of prepping for your first developer job, Big O Notation is a pretty unavoidable topic. Any literature on the topic of procuring employment in the industry will note that a diligent and prepared job-seeker should be able to display some level of competency when touching on the subject.

But if you’re a recent bootcamp grad like myself, hearing all this can leave you feeling fairly perturbed. After all, you just spent a good amount of money and months of your time frantically learning multiple languages at a harried pace in order to change your career, and Big O (or any O for that matter!) was never mentioned. Luckily though, it’s not all that hard to get a very basic understanding of what Big O is all about.

To start thinking about the topic, let’s think about speed. Ideally we want our code to run as fast as possible, right? But how can we judge whether our code is running quickly? For starters, we can test it ourselves by using performance.now() functions in our code. But there are a couple of issues with that…

1. Let’s be honest, you’re not gonna want to do this. If you’re concerned about time, then manually checking the speed of all your functions probably isn’t the best solution for you.
2. It’s not always accurate. Most functions take such a short amount of time to run individually that your computer isn’t going to be able to give you accurate readings. In the graph below the same function is tested multiple times for speed, and as you can see the readings are all over the place.

This is where the idea of Big O notation comes in. Essentially Big O notation allows us a way to formally assume the speed of certain functions. Let’s get into it by looking at a couple of examples:

Both functions above perform the same basic task. They both calculate the sum of all numbers starting at 1 and up to ’n’. On the left, we can see this is achieved by performing a classic for loop, like you probably learned in the first week of your bootcamp (if you were in fact a bootcamper), but on the right the same goal is reached with a much succinct mathematical equation.

Let’s first look at the example on the right with the equation. In this example, let’s count the operations being performed. It looks like there are just three simple mathematical operations in total. Specifically there’s an addition, a multiplication and a division. What’s really important here is that no matter what the value of n is, there will always only be three operations performed.

In terms of Big O notation we would document this as O(1). This is as efficient and speedy as it gets in the world of Big O.

On the other hand let’s look at our old friend the for loop. Unlike in the equation, the amount of operations being performed in the for loop is entirely dependent on the value of n. The greater n is, the more operations that will be performed. They have a directly proportional relationship. In Big O terms, this is O(n).

The value of n effects how often i will be added to the total, and how many ‘less than or equal to n’ evaluations will be performed, as well as how many times each variable needs to be assigned a value. Logically, we can see that if n is a large number, this method gets to be fairly slow, making the function on the right far superior.

It doesn’t matter how many operations are run in a given function either. For example if we look at the function below, we can see that two loops are being run, one after the other. However since the relationship between the number of operations and n is still proportional, we would still just classify the equation as O(n).

However, let’s look at the function directly above. Here we’ve got a fairly icky nested loop. In this instance, what happens if we change the value of n? The amount of operations needed to perform would shoot up dramatically with just small changes in the value of n. In fact, this nested function causes a quadratic relationship — O(n2). So if speed is what you’re after, avoid those nested loops, their bad news!

Above is a chart showing different Big O values and their respective speeds as determined by the value of n. As you can see the O(1) line is straight and horizontal, because it never changes. This is ideal if possible. Where as the O(n) is a straight diagonal line that climbs at a steady rate. Finally, you can see the O(n2) curve represented as a steep exponential curve, rapidly getting slower to perform as n increases.

Of course this is a very basic introduction to Big O, but hopefully now that you understand some of the key ideas of Big O, you have enough to continue exploring the topic and avoid getting completely stumped by an interviewer!