Imagine you’re searching for a friend’s contact in your phone. If you’re scrolling through one by one, it’ll take ages—especially if you have thousands of contacts. But what if you could jump straight to the right section? That’s the magic of efficiency, and it’s exactly what Big-O notation helps us understand.✨

In the world of algorithms, Big-O is like a spotlight, revealing how an algorithm’s performance changes as the size of the input grows. It’s not just a theoretical concept; it’s a practical tool that helps developers write faster, smarter code.

In this blog, we’ll unravel Big-O notation through easy-to-follow examples, moving from simple ideas to more complex scenarios. By the end, you’ll not only grasp the concept but also see how it impacts the code we write every day. Let’s dive in!

So, What Is Big-O, And Why Is It So Important?⭕

Big-O notation is a mathematical way to describe the efficiency of an algorithm, specifically how its run time or space requirements grow as the size of the input increases. It helps us understand how an algorithm performs as the input size scales up, allowing us to predict whether it will run efficiently with large amounts of data.

Rather than focusing on exact run times, Big-O notation provides an abstraction that highlights the growth rate of an algorithm’s time or space complexity. This allows us to compare different algorithms and choose the one that performs best for a given problem.

So Big O provides a standardized way to measure how an algorithm's performance scales with the size of the input data. It's not about nitpicking over milliseconds; it's about understanding the fundamental growth rate of an algorithm.

📌 What’s important to understand here is that Big-O isn’t dependent on the machine you're using or the programming language; it’s a high-level abstraction that tells us how an algorithm will behave as the input size grows, regardless of hardware or implementation details.

O(1)

Here's are first example:

def print(arr):
    print(arr[0]) # 1 unit

This method accepts an array of integers and outputs the first element to the console. It makes no difference how large the array is; it could contain one or a million items. All we are doing here is printing the first item.

This method has a single operation that takes a fixed amount of time to complete. We don't care about the exact execution time in milliseconds because it can vary from one machine to another, or even within the same machine. All we care about is that this method runs in constant time, which we denote as Big O of 1. This is the method's runtime complexity.

In this example, the size of our input doesn't matter—this method will always run in constant time, or O(1).

Now, what if we duplicate this line?

def print(arr):
    print(arr[0]) # 1 unit
    print(arr[0]) # 1 unit

Here, we have two operations. Both of these operations run in constant time, so the runtime complexity of this method is O(2).

📌 However, when discussing runtime complexity, we aren't particularly concerned with the number of operations. We just want to know how much an algorithm slows down as the input size increases. For example, O(1) means that our method runs in the same amount of time whether we have one item or a million. So we can simplify this by writing it as O(1), which means constant time.

O(n)

def print(arr):
    for element in arr:
        print(element)

Here's a slightly more complex example that includes a loop. We're iterating over all the items in this array/list, printing each one to the console. This is where the size of the input is important. If the array contains only one item, we will perform a single print operation. If you have a million items, we will perform a million print operations.

So, the cost of this algorithm increases linearly and in direct proportion to the size of the input. The runtime complexity of this method is represented as Big O of n (O(n)), where n represents the size of the input. This algorithm's cost increases linearly with n.

📌 It doesn't matter what kind of loop you use to iterate through this array. We are using a traditional for loop here. We could also use a for-each or while loop, but the runtime complexity remains O(n).

Now, what if we have a print statement before and after our loop?

def print(arr):
    print("Start")  # O(1)

    for element in arr:  # O(n)
        print(element)

    print("End")  # O(1)

How do you calculate the runtime complexity of this method?

We saw that the single operations (printing "Start" and "End") take constant time, so they are O(1) operations. Our loop completes in O(n). The runtime complexity of this method is O(1) + O(n) + O(1), which can be reduced to O(2 + n). But when using Big O notation, we drop the constants because they are not important.

❓ The Reason: If our array has 1 million inputs, adding two extra operations has no significant impact on the cost of our algorithm; the cost increases linearly. So we simplify it to O(n).

Now, what if you had two loops?

def print(arr):
    for element in arr:  # First loop (O(n))
        print(element)

    for element in arr:  # Second loop (O(n))
        print(element)

What do you think is the runtime complexity of this function?

It is going to be O(n + n) or O(2n). This is another example of dropping the constant, resulting in a runtime complexity of O(n), which still represents linear growth.

📌 Big O notation is used to describe how the runtime of an algorithm increases in relation to the size of the input, particularly as the input size grows larger. The actual value of the constant (such as 2 in O(2n)) has no significant impact on the growth rate. O(n), O(2n), and O(100n) all denote a linear growth rate. While the constant 2 has an impact in practice (for example, an algorithm that runs twice as fast is obviously better), in the context of Big O notation, we simplify O(2n) to O(n) because we're interested in the overall growth trend rather than the exact number of operations.

What if this method had two parameters: a list of numbers and a list of names?

def print(numbers, names):
    for number in numbers:
        print(number)

    for name in names:
        print(name)

What do you think is the runtime complexity here?

Both loops run in O(n). But we have two inputs—numbers and names—rather than just one. So we have to distinguish between these two inputs. We could specify n for the first input and m for the second input.

The time complexity of this method is O(n + m). Again, we can simplify it to O(n) because this method's runtime grows linearly.

O(n^2) & O(n^3)

Simple loops run in linear time, or O(n), as you learnt in the previous example. However, when we use nested loops, the runtime complexity changes. Consider the algorithm for printing all combinations of items in an array.

def print(arr):
    for i in range(len(arr)):            # O(n)
        for j in range(len(arr)):        # O(n)
            print(f"{arr[i]}, {arr[j]}")

Let us analyse the complexity:

• Outer loop: The outer loop iterates through the input array, leading to O(n).
• Inner loop: For each iteration of the outer loop, the inner loop iterates over the array once more, resulting in another **O(n).

Thus, this method has a runtime complexity of O(n * n) = O(n^2). We say that this algorithm runs in quadratic time.

The impact of quadratic time complexity:

As you observe from the analysis, algorithms that run in O(n^2) get slower compared to those that run in O(n), especially as the size of the input grows. For small inputs, the difference may not be noticeable, but as the input size increases, O(n^2) algorithms become significantly slower.

Adding Another Loop to Nested Loops
So, what if we add another loop before or after the nested one?

def print(arr):
    for i in range(len(arr)):              # O(n)
        print(arr[i])

    for i in range(len(arr)):              # O(n)
        for j in range(len(arr)):          # O(n)
            print(f"{arr[i]}, {arr[j]}")

Taking a Look at the Complexity:

• The first loop executes in O(n).
• The nested loop runs in O(n^2) .

This method has a total runtime complexity of O(n) + O(n^2). However, because O(n^2) grows faster than O(n) as input size increases, we eliminate the O(n) term. This method's overall runtime complexity is O(n^2).

More Complex Nested Loops.

What if there's even more nesting?

def print(arr):
    for i in range(len(arr)):              # O(n)
        for j in range(len(arr)):          # O(n)
            for k in range(len(arr)):      # O(n)
                print(f"{arr[i]}, {arr[j]}, {arr[k]}")

Analysing Complexity

• The first loop has a time complexity of O(n).
• The second loop has a time complexity of O(n). The third loop is O(n) as well.

This method has a total runtime complexity of O(n*n*n) = O(n^3). We call this cubic time complexity. As input size increases, this algorithm becomes significantly slower than O(n^2).

Wrapping It Up 🎁

In essence, Big O provides a standardized way to measure how an algorithm's performance scales with the size of the input data. It's not about nitpicking over milliseconds; it's about grasping the bigger picture: the fundamental growth rate of an algorithm. This perspective helps developers make informed decisions, whether it’s choosing the right data structure or designing a scalable system.

We started with constant time and linear time complexities, then dived into nested loops and quadratic time. Each step showed us how an algorithm’s performance can vary based on its structure and design. The best part? You don’t need to memorize every detail. With practice, spotting these patterns will become second nature.

But this is just the beginning! There are other fascinating complexities, like logarithmic time (O(log n)) and exponential time (O(2^n)), waiting to be unraveled. Let me know in the comments if you'd like to explore them further.

All in all, as you write your next piece of code, pause for a moment. Ask yourself: How will this perform with 10 inputs? 1,000? A million? That simple habit will go a long way in sharpening your coding skills.

Until next time—happy coding! 🚀