Big O Categories

This leads us to the next concept within Big O: Big O notation only concerns itself with general categories of algorithm speeds.

As an analogy, let’s talk about physical buildings. There are, of course, many different types of buildings. There are one-floor single-family homes, and two-floor single-family homes, and three-floor single-family homes. There are high-rise apartment buildings with varying numbers of floors. And there are skyscrapers with various heights and shapes.

If we were to compare two buildings, one of which is a single-family home and one of which is a skyscraper, it becomes almost moot to mention how many floors each one has. Because the two buildings are so incredibly different in their sizes and functions, we don’t need to say, “This one is a two-story home, while the other is a one-hundred-floor skyscraper.” We may as well just call one a house and the other a skyscraper. Calling them by their general categories is enough to signify their vast differences.

The same applies to algorithm efficiencies. If we compare, say, an O(N) algorithm with an O(N²) algorithm, the two efficiencies are so different that it doesn’t really matter whether the O(N) algorithm is actually O(2N), or O(N / 2) or even O(100N).

Now, here’s why O(N) and O(N²) are considered two separate categories, while O(N) and O(100N) are part of the same category.

Remember . Big O notation doesn’t care merely about the number of steps an algorithm takes. It cares about the long-term trajectory of the algorithm’s steps as the data increases. O(N) tells a story of straight growth—that the steps increase in a straight line according to some proportion of the data. This is true even when the steps are 100N. O(N²) tells a different story—one of exponential growth.

Exponential growth is a completely different category compared to any form of O(N). This point is really driven home when we consider that O(N²) will, at some point in data growth, become slower than O(N) multiplied by any factor.

In the following graph, you can see how O(N²) becomes slower than various factors of N:

Therefore, when comparing two efficiencies that belong to two different categories of Big O, it’s enough to identify them by their general category. Talking about O(2N) when compared to O(N²) is like talking about a two-story house compared to a skyscraper. We may as well just say that O(2N) is part of the general category of O(N).

All the types of Big O we’ve encountered, whether it’s O(1), O(log N), O(N), O(N²), or the types we’ll encounter later in this book, are general categories of Big O that are widely different from each other. Multiplying or dividing the number of steps by a regular number doesn’t make them change to another category.

However, when two algorithms fall under the same classification of Big O, it doesn’t necessarily mean that both algorithms have the same speed. After all, Bubble Sort is twice as slow as Selection Sort even though both are O(N²). So while Big O is perfect for contrasting algorithms that fall under different classifications of Big O, when two algorithms fall under the same classification, further analysis is required to determine which algorithm is faster.

A Practical Example

Let’s return to the first code example from Chapter 1, with minor changes:

Here we have two algorithms for accomplishing the same task, namely printing all even numbers starting from 2 to some upper_limit. (In Chapter 1, the upper limit was fixed at 100, while here, we let the user pass in a number as the upper_limit.)

I noted in Chapter 1 that the first version takes twice as many steps as the second version, but now let’s see how this plays out in terms of Big O.

Again, Big O expresses the answer to the key question: if there are N data elements, how many steps will the algorithm take? In this case, though, N isn’t the size of an array, but simply the number we pass into the function to serve as the upper_limit.

The first version takes about N steps. That is, if the upper_limit is 100, the function takes about 100 steps. (It really takes 99 steps, since it starts the count at 2.) So we can safely say that the first algorithm has a time complexity of O(N).

The second version takes N / 2 steps. When the upper_limit is 100, the function takes just 50 steps. While it would be tempting to call this O(N / 2), you’ve now learned that we drop the constants and reduce the expression to O(N).

Now, the second version is twice as fast as the first one and would naturally be the better choice. This is another great example of where two algorithms can be expressed the same way using Big O notation but further analysis is needed to figure out which algorithm is faster.

Significant Steps

Let’s apply one more level of analysis to the previous example. If we look again at the first version, print_numbers_version_one, we said that it takes N steps. This is because the loop runs N times, with N being the upper_limit.

But does the function really take just N steps?

If we really break things down, we can see that multiple steps occur in each round of the loop.

First, we have the comparison step (if number % 2 == 0), which checks whether the number is divisible by 2. This comparison happens in each round of the loop.

Second, we have the print step (print(number)), which happens just for the even numbers. This, then, occurs in every other round of the loop.

And third, we have number += 1, which runs in each round of the loop.

In the previous chapters, I alluded to the fact that you’d learn how to determine which steps are significant enough to be counted when expressing the Big O of an algorithm. In our case, then, which of these steps are considered significant? Do we care about the comparisons, the printing, or the incrementing of number?

The answer is that all steps are significant. It’s just that when we express the steps in Big O terms, we drop the constants and thereby simplify the expression.

Let’s apply this here. If we count all the steps, we have N comparisons, N incrementings, and N / 2 printings. This adds up to 2.5N steps. However, because we eliminate the constant of 2.5, we express this as O(N). So which step was significant? They all were, but by dropping the constant, we effectively focus more on the number of times the loop runs, rather than the exact details of what happens within the loop.