Rewbie Newbie

Documenting my path on becoming a Rails Developer.

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.

1
2
3
4
5
6
O(1) efficiency

1 item:         1 second
100 items:      1 second
10000 items:    1 second
1000000 items:  1 second

Ο(log2 n)

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

1
2
3
4
5
6
O(log n) efficiency

1 item:         very small fraction of a second
100 items:      6.64 seconds
10000 items:    13.29 seconds
1000000 items:  19.93 seconds

Ο(n)

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

1
2
3
4
5
6
O(n) efficiency

1 item:         1 second
100 items:      100 seconds
10000 items:    10000 seconds
1000000 items:  1000000 seconds

Ο(n log2 n)

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

1
2
3
4
5
6
O(n log n) efficiency

1 item:         very small fraction of a second
100 items:      664.39 seconds
10000 items:    132877.12 seconds
1000000 items:  19931568.57 seconds

Ο(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.

1
2
3
4
5
6
O(n**2) efficiency

1 item:         1 second
100 items:      10000 seconds
10000 items:    100000000 seconds
1000000 items:  1000000000000 seconds

Ο(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.

1
2
3
4
5
6
O(2**n) efficiency

1 item:         1 second
100 items:      1267650600228229401496703205376 seconds
10000 items:    Too big to print.
1000000 items:  Too big to print.

Ο(n!)

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

1
2
3
4
5
6
7
8
O(n!) efficiency

1 item:         1 second
10 items:       3628800 seconds
40 items:       815915283247897734345611269596115894272000000000 seconds
100 items:      Too big to print.
10000 items:    Too big to print.
1000000 items:  Too big to print.

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!)