The secret of big O notation

⚡ TL;DR: Big O notation helps us describe the efficiency of algorithms. It will help you make a more informed decision as to which algorithm is right for your specific use case. In addition, you'll likely be expected to know this in any technical interview.

Which one do you choose? 🤔

Imagine you're getting ready to download Animal Crossing to play with a group of friends. You don't think twice about it, you click "Install" and a few minutes later it's ready to play.
But now, you hear Drake is having a concert on Fortnite on Saturday. You're super excited, he just dropped his new album. You have to see that! Now think about this. Fortnite is about 20GB.
Assuming you have a somewhat decent internet connection, it could still take up to 3 days to download it! Amazon offers next day delivery for the physical copy of Fortnite #AmazonPrime.

We can see how in some cases it might be faster to get a game from Amazon, and in some cases it's just faster to download it. But regardless of the game's size, getting it from Amazon with next-day delivery is always going to take the same amount of time. Downloading a game on the other hand, varies based on its size.

In this case, Amazon takes O(1) time to get a game (it's constant!), and downloading it is O(n), n being the size of the game: the bigger the game, the longer it will take.

O(1), O(n), what does that even mean? 🤷‍♀️

The big O notation is used to classify time and space requirements of your algorithms.

Here are some rules to remember when trying to find the complexity of an algorithm:

• Always drop constant terms.

function twoLoops(n) {
    for (let i = 0; i < n; i++) {
        console.log(i); // First loop, O(n)
    }
    for (let j = 0; j < n; j++) {
        console.log(j); // Second loop, also O(n)
    }
}

Here, our twoLoops function iterates n times twice. What do you think the big O notation for this function should be?

Intuitively, we could start by saying that it is O(2n): the first loop is O(n) and the second loop is also O(n), adding them up we get 2 ✕ O(n) or O(2n).

With out first rules, we know that constant terms (here, 2) must disappear. So our big O complexity is actually O(n).

• Always drop non-dominant terms.

function nestedLoops(n) {
    for (let i = 0; i < n; i++) {
        console.log(i); // First loop, O(n)
    }

    for (let x = 0; x < n; x++) {
        for (let y = 0; y < n; y++) {
            console.log(j); // Nested loop, O(n²)
        }
    }
}

In this example we still have the first loop but we also have a nested loop. Adding those two big O together, we would get O(n + n²).

This rule tells us that since n² "dominates" (it's the biggest term), we need to remove any other term. We end up with O(n²), exponential growth.

💡 Did you know? Big O has a few siblings, including the little o and big Omega notations, which are other examples of asymptotic notations. However, in the case of technical interviews, big O is the most useful.

Space AND Time complexity

In an interview setting, you'll likely be asked to talk about the big O complexity of the solution you provided to a problem.

• Space complexity measures the space growth of your algorithm. It helps you answer the question "How much space will my algorithm require relative to the size of the input?".
• Time complexity measures the runtime growth of your algorithm. It helps you answer the question "How much time will my algorithm run relative to the size of the input?".

function badFibonacci(n) {
    const arr = [0, 1];

    for (let i = 2; i <= n; i++) {
        arr.push(arr[i - 2] + arr[i - 1]);
    }

    console.log("arr length:", arr.length);

    return arr[n - 1];
}
> badFibonacci(5)
arr length: 6
3
> badFibonacci(9)
arr length: 10
21

How could we go about calculating the big O complexity here?

For space complexity, we need to look at the variables we're using: arr and i. i doesn't change in size, it's constant. Knowing our rule about constants, we can ignore it.

arr however, is different: its size is going to grow relative to n. The bigger the n, the larger the array: this is linear growth, O(n).

To calculate the time complexity, we look at the number of steps taken to reach the solution. In this case, there is a single loop that grows relative to n, which means our big O complexity is also O(n).

When you see this, you might not necessarily think that anything is wrong with this solution. After all, it does what you want it to do.

But in an interview setting, you always have to ask yourself: can this solution be better?

🚨 Your first solution is often a Brute Force approach. You just want to get the code working. Once you have identified a solution, you'll want to optimize it, improving its runtime and space requirements.
Depending on the problem at hand, you'll know what type of solution you need to provide.

Tradeoffs

In most cases, when optimizing a solution, you are going to make tradeoffs: give up speed, to lessen space requirements, or give up space, to improve speed.

🚨 This is an important talking point during your interview to be able to explain your optimization choices in terms of tradeoffs.

Best or worst case scenario?

function badFindIndex(needle, haystack) {
    for (let i = 0; i < haystack.length; i++) {
        if (needle === haystack[i]) {
            return i;
        }
    }

    return null;
}
> badFindIndex("a", ["a", "b", "c"]);
0
> badFindIndex("z", ["a", "b", "c"]);
null

In this example, the best case scenario is when needle is the first element of haystack: we don't have to traverse the rest of the array in order to find the target.

For the worst case scenario, needle is not in the haystack. However, we have to traverse the entire array just to confirm it's not present.

🚨 The array is really small here, but in an interview setting, you have to think big! Google has databases with billions of records -- try to think of these kind of scenarios when optimizing your solution.

When calculating big O, always think of the worst case scenario!

Conclusion

To wrap things up, the secret to big O notation is knowing how to choose the right algorithm while considering factors such as space and time complexity, tradeoffs and best and worst case scenarios.

Hopefully, you now feel prepared for your next technical interview!

What did you think of the post? Did you learn anything new? We would love to hear from you!

If you are still looking for more practice, be on the lookout for our next post. We will solve a popular interview coding problem from leetcode.

Also there is a free computer science course on EdX taught by Hardvard professors where you will learn fundamental principles. It's a great resume builder and you get a certificate at the end of the course!

As an added bonus, here's a big O cheatsheet we made! 🔥