Comparing algorithms with big O

Suppose you need to choose one of several algorithms to solve a problem. How can you pick the best one? To do it, you need to measure the algorithm efficiency somehow.

One of the options might be to measure the time your program needs to process its input. However, different computers may take different times to process the same data. Furthermore, the processing time may depend on the data itself. We obviously need something more universal. So, let's try to estimate the efficiency using Big O notation.

Input size

What does an algorithm usually do? It makes some calculations. Let's call constant-time operations the basic actions, such as addition, multiplication, comparison, variable assignment, etc. Of course, the calculation time depends on the machine, but it doesn't matter now because we want to compare algorithms, not machines. Now let's try to estimate the number of operations in an algorithm!

Buses aren't always punctual, are they? One day it may happen that they are there on time, while the other day they will take a lifetime to arrive. You can't blame the driver for that solely: the trip time depends directly on the number of passengers on the bus. The more passengers, the more stops, and the longer the time to arrive. Likewise, the running time of an algorithm depends on the input data. Naturally, the program will take a different time to proceed with $10$ or $1\ 000\ 000$ numbers. We will use the term input size as a proxy measure of the size of input data. If you need to work with $m$ numbers, then $m$ is the input size. The input size isn't always the amount of the input data itself. If you need to find the first $n$ prime numbers, then searching for $10$ first primes or $10\ 000$ first primes will also take a different time, however, you only enter a single number $n$ as input. In such cases, that number's value is typically considered the input size.

If we can estimate how the number of operations depends on the input size, we will have a machine-independent measure of algorithm complexity. This is exactly what we need! Also, if we want to find a good algorithm, we are mostly interested in its behavior with big data. For this, we can compare the behavior of the algorithm's running time with some standard functions.

Understanding complexity from code

Big O notation is like a shorthand for talking about how fast an algorithm grows as the input size increases. It helps us describe whether an algorithm gets slower in a predictable way as we give it more stuff to work with, without worrying about the exact details of the timing. Essentially, it's a way to compare and understand the "bigness" of algorithms in a simple and easy-to-understand manner. Let's explore this concept through pseudocode examples:

Linear complexity occurs when an algorithm's execution time grows linearly with the input size $n$. Each iteration of the loop performs constant-time operations, and as the input size increases, the execution time increases proportionally:

for i = 1 to n:
    // Constant-time operations
    // ...

Nested loops, as in the example below, lead to a quadratic time complexity $O(n^2)$, because for each iteration of the outer loop, the inner loop iterates through the entire range of $n$, resulting in $n^2$ total iterations:

for i = 1 to n:
    for j = 1 to n:
        // Constant-time operations
        // ...

What if there are various loops, not related to each other? We, obviously, take into account the one that takes more time. So, in the case below, the complexity will be quadratic, since the second loop takes longer than the first one:

// first linear loop
for i = 1 to n:
    // Constant-time operations
    // ...

// second quadratic loop
for i = 1 to n:
    for j = 1 to n:
        // Constant-time operations
        // ...

Common growth rates

Below are, from best to worst, some common values of the Big O function for the time complexity, also known as complexity classes.

• $O(1)$ (constant time). The algorithm performs a constant number of operations. Maybe one, two, twenty-six, or two hundred – it doesn't matter. What is important is that it doesn't depend on the input size. Typical algorithms of this class include calculating the answer using a direct formula, printing a couple of values, all letters of the English alphabet, etc.

• $O(\log n)$ (logarithmic time). Perhaps a quick reminder on logarithms is necessary. We usually refer to the logarithms of base 2; however, the base does not affect the class. By definition, $\log_2n$ equals the number of times $n$ must be divided by $2$ to get $1$. That being said, it should not be difficult to guess that such algorithms divide the input size into halves at each step. They are relatively fast: if the size of the input is huge, say, $2^{31}$ (programmers should know the importance of this number), the algorithm will perform approximately $\log_2(2^{31}) = 31$ operations, which is pretty effective.

• $O(n)$ (linear time). The time is proportional to the input size, i.e., the time grows linearly as the input size increases. Often, such algorithms are iterated only once. They occur quite frequently because it is usually necessary to go through every input element before calculating the final answer. This makes the $O(n)$ class one of the most effective classes in practice.

• $O(n^2)$ (quadratic time). Normally, such algorithms go through all pairs of input elements. Why? Well, mathematics is generous, it constantly provides us with important results: in this case, basic math confirms that the number of unordered pairs in a set of $n$ elements is equal to $\frac{n(n-1)}{2}$, which, as we will learn in the following topic, is $O(n^2)$. If you find it scary or difficult to understand, it is completely normal, it happens to the best of us.

• $O(2^n)$ (exponential time). Just in case, let's mention that $2^n$ is the same as multiplying $2$ by itself $n$ times. Again, math states that the number of subsets of a set of $n$ elements is equal to $2^n$, therefore, it is reasonable to expect that such algorithms scan all the subsets of the input elements. It is worth noting that this class is extremely inefficient in practice; even for small input sizes, the time taken by the algorithm will be remarkably high.

More growth rates

There are other less common complexity classes, which you will come across in the following topics:

• $O(\sqrt n)$ (square root time);

• $O(n \log n)$ (log-linear time);

• $O(n^k)$ (polynomial time);

• $O(n!)$ (factorial time).

Now let's gather all the classes together and sort them from the best to the worst so that you remember which ones are the most effective, and which ones you should stay away from.

It is worth noting, that in practical terms, an algorithm with worse theoretical complexity might perform better for small inputs due to optimizations. However, we focus on large values of $n$ because Big O notation helps us understand how an algorithm behaves as the input size approaches infinity. This gives us insights into its long-term efficiency trends, which become increasingly important as data or workloads grow significantly.

Conclusion

Let's recap what we've learned in this topic:

• Big O notation serves as a useful tool for visually representing the efficiency of an algorithm in relation to the size of its input.
• Time complexity is a metric used to quantify how complex an algorithm is in terms of its execution time.
• It's essential to understand that lower time complexity values translate to faster performance. However, it's not always feasible to reduce an algorithm's complexity, as some problems inherently require certain levels of complexity.
• We commonly encounter several time complexities, including constant, logarithmic, linear, quadratic, and exponential. Each of these categories represents a different relationship between input size and computational effort.
• The reason we care so much about time complexity is that we aim to make our code run as efficiently as possible. Swift and efficient code not only saves computational resources but also ensures a pleasant user experience. An unsatisfied user, faced with slow software, is more likely to switch to a competitor's product, which can have a detrimental impact on your income or your company's success.