Algorithm Complexity and Big O Notation

Let’s discuss algorithms complexity, and in particular how we measure it in the context of algorithms.

Different algorithms, given the same problem to solve and the same inputs, take a different time to solve the problem.

Sometimes, a hugely different time, especially as the number of elements they need to manage grows.

This complexity is called Big O, for no other reason that we use an upper case o letter as a convention: O(n), O(1) and so on.

The most popular measures of Big O you will see, sorted by more efficient to less efficient, are:

• O(1)
• O(log n)
• O(n)
• O(n * log n)
• O(n^2)
• O(n!)

where n is the number of inputs. For example, if you need to sort 2 items n is 2, and if you need to sort 20.000 items, n is 20.000.

But you don’t need to substitute the value in the O() calculation. That is a symbol, meant to signal developers and everyone looking at the algorithms its efficiency.

An algorithm with O(1) efficiency is the best possible one we can find. The time to execute does not depend on the number of inputs, it always takes the same time to execute

An algorithm with O(n) scales linearly with the number of inputs. If with 10 items it takes 1 second, with 100 items it will take 10 seconds.

An algorithm with O(n^2), if with 4 items takes 16 seconds, with 10 items takes 100 seconds.

We will analyze and calculate the Big O efficiency of a good number of algorithms in the next lessons.

It’s important to note that Big O notation does not give us all the information we need to judge whether an algorithm will be faster than another, in particular if their Big O value is the same. In this case, you will need to use other tools to test the efficiency.

But when algorithms have different classes (O(n) vs O(n^2) for example), there’s no doubt.