The Big O

Time Complexity of Your Code

One of the most useful data points post coding boot-camp has been going through a mock technical interview on Skilled-Inc. It can be an incredibly nerve-wracking experience, but going through one of these mock interviews can help tremendously in identifying gaps in your knowledge. Gaps that you can fill as you work towards become a better and more complete programmer.

One big gap was my understanding of the Big O.

Code Performance and Complexity

To provide some context, Big O describes the worst-case scenario regarding the execution time required or the space used (e.g. in memory or on disk) by an algorithm. It’s a short-hand way of us being able to communicate what happens with our code as more and more people use it.

For example, your code might work ok when just 1000 or 2,000 people use it. But what about when a 1,000,000? Or even 1,000,000,000?

To learn more about this, here’s a chart with some fancy mathematical notations on the right.

The math stuff on the right might seem a bit intimidating, but it’s actually super simple. Let’s start by explaining some of the axis.

X-Axis: Elements represent how many “things” run your code.

For example, you have array = [1,2,3], so you have 3 “things” in it. Let’s say these are users for your awesome new site.

But suddenly, your site gets featured on Product Hunt. Or maybe BuzzFeed links to you. Or Google somehow has you as the #1 result for cat gifs. Your array becomes larger and larger until it reaches “N” size. That’s essentially what’s happening to our chart.

Y-Axis: Operations represent how many “actions” code has per element.

These “actions” can be anything. You should think about it as any kind of calculation that needs to be made per element in your array.

For example, let’s say whenever a person logs into your site they should see a list of their favorite foods and friends.

favorite_food_array = [fried chicken, mac n cheese, vegan tofu, beer]

Pretty simple. If we were explaining this with pseudo-code, our code would:

  1. Look through the entire list of foods
  2. Return only foods that are your favorites

So here’s the question. What’s Big O here? How do we calculate a “time” complexity associated with these actions from our code?

Remember we assume the number of elements in our array approach “N”. This means we have to start thinking in terms of how long it takes to complete our actions or calculations in terms of N.

So in our favorite_food_array there are two steps, but we’re really only doing one calculation: is this food in my favorites or not?

That means we only have one calculation PER ELEMENT in our array.

As a result, our time complexity is equal to O(N).

Hey! Remember that fancy chart we had? Turns out that O(N) is just a linear relationship. Every element we have, we take one action.

If Big O still seems a bit fuzzy, let’s do another example!

We’ve got our favorite_food_array showing up when a person logs on, but let’s say we also want to show a list of our friends as well

favorite_food_array = [fried chicken, mac n cheese, vegan tofu, beer]
friends_array = [Fry, Leela, Bender, Farnsworth]

So what’s our calculations doing now? Think about using pseudo-code here as well:

  1. Look through the entire list of foods
  2. Return only foods that are your favorites
  3. Look through entire list of people
  4. Return only people in your friends list

Hey! The steps in our friends_array look really similar to or favorite_foods_array. In fact, they are exactly the same.

So what does this mean in our Big O notation now?

To simplify this, let’s assume both our friends_array and favorite_foods_array both approach “N”. How many food items would we need to look at and calculate whether it was in our favorites?

N

Now think about how many people we would need to look at to calculate whether they are in our friends list.

N

This means that our total time complexity is N+N = 2N

In other words:

Our Time Complexity is O(2N)

Time to Get Real

So now you understand basic linear time complexity. Let’s kick it up a notch.

In our previous example, what if we only wanted to show our friends who also have the same favorite food as we do? Let’s use some pseudo code to walk through this. Basically your code would have to:

  1. Look through the entire list of foods
  2. Return only foods that are your favorites
  3. Look through entire list of people
  4. Return only people in your friends list
  5. Look through each of your friends in your friends_array
  6. Return your friend’s favorite_food_array
  7. Look through each of the foods in your friend’s favorite_food_array
  8. Return only friends who have the same favorite_food_array as you.

Phew, not bad. But see see how we almost DOUBLED the number of steps we have now? That should already tell us that the complexity of this is much higher than it was before.

So how do we think about calculating the complexity of this? Well, for starters it’s no longer linear. Why not?

Think about step 5 and step 7. Here you’re looking through an array of friends to find an array of foods. This means you’re actually looking through two arrays that are nested within one another.

Remember how we said time complexity is just a fancy way of saying “how many times did you perform an action”? Let’s use some examples here.

Say we have 3 friends in our array and they have 3 foods in their favorite_foods_array. How many “actions” do we go through before we’re done? I’ve simplified it below for you:

Friend 1 :Food 1 / Friend 1 : Food 2 / Friend 1: Food 3
Friend 2:Food 1 / Friend 2: Food 2 / Friend 2: Food 3
Friend 3:Food 1 / Friend 3: Food 2 / Friend 3: Food 3

We have a total of 9 “actions” since we have to look at each food element for each friend. So what happens when we have N friends and N favorite foods?

If you thought N² then you are correct!

This means our time complexity is O(N²)

Let’s take a look at our fancy chart again. There’s an enormous difference between our green O(N) line and our blue O(N²) line. What this should show you is that trying to do “brute force” calculations across nested arrays is a HUGE time cost. Later on, I’ll write about how we resolve some of these issues with different types of algorithms.

Until then, I hope you go a chance to learn about the importance of understanding Big O and how it can affect your code.