Understanding the Base of a Logarithm

Before explaining Big O notation, it's necessary to explain what a logarithm is. A logarithm asks how many multiplications of the same number X are needed to reach a number Y.

Ex: \(2^x = 8\) How many 2s do I need to multiply to get 8? \(2^3 = 8\)

Which means that \(Log_{2}(8) = 3\). The number under Log, 2, is the base (the number to multiply by); the number in parentheses, 8, is the number you want to reach; the result, 3, is how many times you have to multiply the base (in this case, 2).

Another example would be the logarithm of 1024, where you have to compute the exponent needed to reach that number, i.e., \(2^x = 1024\).

$$2^{10} = 1024 == Log_{2}(1024) = 10$$

There are other logarithms such as \(Log_{10}\), which would compute \(10^x\), but understanding \(Log_{2}\) is enough.

Introduction

Big O notation is the representation of how an algorithm scales as the amount of input grows; it represents how fast the algorithm is.

That is, you can have two algorithms, and one can grow exponentially more than the other. For example.

You can clearly see how linear search increases its time much more than binary search when you add more elements.

Big \(O(n)\) and \(O(log(n))\)

Linear search means it has to go element by element until it finds the item it's looking for. It starts with the first element—Is it the one I'm looking for? No—move to the second element, and so on until it finds the item.

Therefore, for a list of \(n\) elements, the number of checks it may need to perform is \(n\) times in the worst case (i.e., the item is last). This means that for linear search, the Big O notation is \(O(n)\). Big O can be measured for the “best case,” the “average case,” and the “worst case.” But the most common—and the one we will always refer to in this post—is the “worst case”.

To see an example of \(O(log(n))\), let's understand binary search, which starts from a sorted list:

[1, 2, 3, 4, 5, 6, 7].

Suppose we are searching for the number 5 with binary search; here's how it works:

In the case of binary search, the number of elements in the list is not the same as the number of checks we need to perform. The example above is a worst case, and it only took 3 iterations to obtain the worst case (5). The worst case could be any of these \(1, 3, 5, 7\) in a list of 7. In contrast, in a linear search, the worst case for a list of 7 would be 7 iterations.

Since the number of iterations depends on the algorithm, this algorithm's Big O notation is \(O(log(n))\), which means it's faster than linear search.

Big \(O(n!)\), \(O(n^2)\), and \(O(1)\)

Here is a graph where you can see all the Big O notations and how the number of operations grows as the algorithm's input size (such as the size of a list) increases.

In the previous examples, we saw an \(O(n)\) algorithm (linear search) and an \(O(log(n))\) algorithm (binary search).

Now let's look at the ones that are left: \(O(n!)\), \(O(n^2)\), and \(O(1)\).

\(O(1)\)

\(O(1)\) is the simplest: this is an algorithm that completes in a single operation. For example, looking up an object by its key in a Map.

        Map<String, String> dniMap = Map.of(
                "12345678A", "María Lopez Marrero",
                "87654321B", "Juan Pérez Armas"
        );
        String nameClient = dniMap.get("12345678A"); // This is O(1), even if the map size is 100
        System.out.println(nameClient); // "María Lopez Marrero"

\(O(n^2)\)

This O means it grows quadratically. A very simple example would be a typical double nested loop, i.e., a for inside another for. The outer loop runs \(n\) times, and for each iteration of the outer loop, the inner loop also runs \(n\) times. This results in a total of \(n * n = n^2\) operations in the worst case.

There are several sorting algorithms with this notation; one of the most famous is Bubble Sort. This algorithm compares the first element with the second and, if the first is larger, it swaps them; then it compares the second with the third, and so on until the end. The largest element is guaranteed to be in the last position. Therefore, on the next pass, we only need to sort up to the penultimate element; with each iteration, you traverse \(n - 1\) in the worst case.

\(O(n!)\)

Factorial time is the slowest among common Big O behaviors, so we should always avoid having our algorithms reach this point. Interestingly, there are problems for which, so far, there is no more efficient way to solve them than with an algorithm whose notation is \(O(n!)\).

The example I'll present is called the traveling salesperson problem. In my example, it's a mail courier to be a bit more current. Suppose we have to deliver 5 packages to their respective 5 destinations. How can we know which is the shortest route to deliver the packages? If there are 5 locations, the route combinations are 120.

$$(5! = 5 \times 4 \times 3 \times 2 \times 1 = 120)$$

As you can see from the factorial formula, each time we add one more stop, the number of possibilities increases dramatically.

Therefore, the only way to compute the shortest route is to calculate the total distance for every possible route and, once we have them all, keep the minimum. As you can see, in this case it's very hard—if not impossible—to get below \(O(n!)\). Here's a link with more information if you want to learn more about the travelling salesperson problem.

Conclusion

In this post, you've seen what a logarithm is, what Big O notation is, and an explanation with a practical example of each Big O. I hope it helped you make your programs faster 🚀