Hello and welcome to my first Mirror post! This post is a copy of the LinkedIn article I wrote in 2020. Back then, I intended on updating and continuing this post. I will not be doing that. I hope you find this article informative and inspire you to delve deeper.

It doesn't matter whether you're self-taught or you went to school to study computer science. If you're looking to be hired as a software engineer, you're going to need to understand Big O notation along with calculating time/space complexity.

There's a high probability that a question, such as "Can you tell me the time/space complexity of this algorithm?" or "What's the Big O of this function?" will appear in your next technical interview.

My intention with writing this article is to help you understand Big O notation so that when the time comes and you're in a technical interview... you'll feel confident in answering a question about time/space complexity and Big O notation.

What is Big O notation?

We use Big O notation to determine how fast an algorithm's runtime is, as the number of operations/inputs for that algorithm increases.

By knowing the Big O of our algorithm, we're able to:

• Know how well our algorithm performs as the number of operations increases (in its worst-case scenario).
• Compare algorithms to determine which algorithm is faster and takes less memory.

I want to emphasize, when we use Big O notation, we're discovering how efficient an algorithm is in its worst-case runtime.

How is Big O notation written and said?

Depending on the algorithm, you'll see Big O notation written in a variety of forms like this: O(n), O(1), O(log n), and more. "n" in this case, is the number of operations in an algorithm. The speed of an algorithm isn’t measured in seconds but in the growth of the number of operations.

But, how would you tell somebody that an algorithm has a Big O notation of O(n), O(1), O(log n)?

Give it a try (I encourage you to say it out loud):

• O(n) = Big O of n.
• O(1) = Big O of one.
• O(log n) = Big O of log n.

Most times, you can leave out the word "Big" and just say O of ...

Why does it matter if we use Big O notation?

There's a time and place to use Big O notation.

If your goal is to create an application that doesn't require a lot of operations/inputs and more people won't be using it then you're most likely not going to have to stress out about Big O notation. But, if you're working at a company such as Amazon, Google, Facebook, Twitter, etc... your job will require you to design algorithms that'll be used by millions.

When millions of people are using software that relies on your algorithm, you're going to want to start asking yourself questions such as:

• Is my algorithm readable?
• Is my algorithm fast?
• Can I reduce the number of operations my algorithm does while maintaining readability and speed?
• How much memory is my algorithm taking?

There are always limits to how much you can improve in one area before another area starts suffering. And what I mean by this is, if I focus purely on making my algorithm as fast as possible, there's a good chance that my algorithm won't be as easy to read or my algorithm may require more space in trade for more speed.

These are the types of things you must consider when designing your algorithms and by thinking about these things, they make you a better engineer.

Speed isn't everything

Obviously, you want your code to be fast, but you also want to be able to come back to your code (or have somebody with fresh eyes) nine months later and be able to understand what your code is doing.

Consider Big O notation as something that you can add to your software engineering toolkit. You have a bunch of tools in your toolbox such as data structures, design patterns, and sorting algorithms. You then use these tools in your toolbox to create different types of algorithms. Now you're able to use Big O notation to compare the algorithms you've created with each other to select the algorithm that'll better fit your need.

Before we start moving onto time and space complexities, I think it's important to mention that the reason why it's incredibly important to use something like Big O notation, especially when building for scalability is that everything seems fast when there's only a small amount of inputs and operations being done. It's only when you get to large amounts of inputs and operations that you can really see how efficient your algorithm really is.

Big-O Complexity Chart

Before we get into calculating and understanding time and space complexities, above is a chart courtesy of (https://www.bigocheatsheet.com) which shows us the complexities of common algorithms. I recommend bookmarking this website as it helps remember the complexities and how they perform.

How do we use this chart?

When we figure out the Big O notation of our algorithm, we're able to use this chart to identify how our algorithm performs either in time or space complexity. For example, If we figure out that our algorithm is O(n), we can look at this chart to find the line representing O(n). Notice that as the number of elements increases (goes further to the right along the x-axis), we notice that the number of operations (y-axis) doesn't increase as much. The chart says that an algorithm with O(n)... is fair.

Time complexity

Big O notation can be used for describing two things: Time complexity and Space complexity. It's important to know how to find and describe both of them using Big O notation.

How to find the time complexity in Big O notation

We find the time complexity by counting the number of operations in an algorithm and then using a chart like above to determine whether that time complexity is good or bad.

Our first complexity, O(1) - Constant Time

In this example, I have a function named functionOne. In it, I initialized an integer named total and set it equal to 42. Afterward, I logged the total to the console.

There were two operations done, each of these operations was O(1). There were no loops at all, very quickly we initialized an integer and displayed it to the console. Every time we invoke this function, it will always be "O of one". Having a time complexity, O of one.

You may have noticed that when we counted the total amount of operations it was O(2) but I said this function was O(1) - Constant Time. There are some simplifying rules that I will get to later. For now, know that this is an example of what constant time and a time complexity of O(1) looks like... no loops. It's important to remember that O(1) stands for Constant Time.

Here are some more examples of O(1) - Constant Time

This graph represents O(1), every time we invoke a function with time complexity of O(1), we know that it's going to be really fast because the number of operations is the same each time. Notice that the line is a horizontal line at 1?

What if our algorithm was O(2)? Then we'd have a horizontal line at y = 2, it'd still be a horizontal line with no changes in the number of operations. So if we see any constants e.g. O(500), O(32), O(17), etc... we always simplify it to O(1) because O(1) has the same behavior as any other constant.

Our second complexity, O(n) - Linear Time

This is our second complexity, O(n) - Linear Time. A loop is considered O(n).

Do you remember what the n stands for in O(n)?

n stands for: # of operations

A loop is considered O(n) because a loop would typically go through the loop, n amount of times. Even if you change the number of times you want to loop through the loop it still results in looping n amount of times. As a result, this is known as linear time. As the number of elements(inputs) increases, the number of operations increases.

O(n) Linear Time = for loops, while loops through n items.

In linear time, as the number of elements increases, the number of operations increases, and time complexity is longer.

Our third complexity, O(n²) - Quadratic Time

Looking at our Big O cheatsheet, notice that the Quadratic Time complexity is in the red. It's horrible. For example, if we have 400 operations, we end up having, 160,000 operations. Now we're starting to have a better understanding of why Big O notation is important especially when dealing with scalability.

Thank you for reading.