The Big O Notation

The big O notation is used to denote the approximate effiency of an algorithm when the algorithm is applied on an arbitrarily large dataset. In other words, it give you a sense of how effiencient an algorithm is when it is applied on a small dataset compared to a very large dataset.

The effiency of an algorithm is measured either by the amount of time (speed) or the amount of memory the algorithm uses when executed. The aim of the big O is to capture the upper-bound or worst-case performance effciency of an algorithm.

The formal definition of the big O notation is much more complex than the application of the concept, so this is a topic best dealt with examples rather than getting tangled up in the intricacies of defining it.

Before we jump into the examples, let’s lay down some ground rules. Items will refer to the number of items in a dataset. Seconds is used as an arbitrary time unit to give a relative sense of how long it takes an algorithm to execute depending on the size of the dataset. The use of seconds does not at all reflect computation time, nanoseconds can be used to substituted for seconds, but I’ve chosen seconds because it’s much easier to relate to than a nanosecond, plus it’s shorter to type. Lastly, the hypothetical algorithm in each example is to be viewed independent of each other, the focus is not on the algorithm, but rather on how big O captures the efficiency of the each algorithm given varying dataset sizes.

Ο(1)

First off, the best case scenario is that an algorithm operates in Ο(1), which means it finishes executing in the same amount of time regardless of the size of the input dataset.

Ο(log2 n)

Ο(log2 n) is not as efficient as Ο(1), but it can handle large datasets almost as well.

Ο(n)

Ο(n) grows linearly, which means for each item added to the dataset, the execution time increases by one second.

Ο(n log2 n)

Ο(n log2 n) is not as efficient as Ο(n), but it is not amongst the worst either.

Ο(n2) or Ο(na) where a is any integer >= 2

Ο(na) applies to any algorithm whose efficiency grows by a factor of a polynomial. The most common efficiency is the quadratic-time efficiency, and as you can see below, any algorithm with a polynomial effiency quickly deteriorates as the dataset size increases.

Ο(2^n)

An algorithm with Ο(2^n) effiency becomes unusable even quicker as the dataset increases. The addition of each item doubles the execution time.

Ο(n!)

Ο(n!) effiency breaksdown very quickly. The execution time explodes even when the dataset size is still relatively small.

Conclusion

In terms of effienciency, the list of the most common big Ο can be summed up as:

Ο(1)  >  Ο(log2 n)  >  Ο(n)  >  Ο(n log2 n)  >  Ο(n2)  >  Ο(2n)  >  Ο(n!)