The Big O notation – Summary

Big O notation was invented to describe the growth rate of a function. You basically take away all constants and small factors and only focus on the big factors. Let’s take an example; the function:

x^2 + 2x + 6

in terms of big O notation becomes:

O(x^2)

We use this notation to describe the growth rate of algorithms too. A brute force algorithm that checks each and every object against the next is called O(n^2) (quadratic growth). If you have 100 objects, you will have to do 100^2 = 10.000 checks.

Having a O(n log(n)) algorithm is obviously better as it grows slower. If you have the same 100 objects, you will only have to do 100 * log(100) = 200 checks!

To give a graphical view of the growth. X is the number of objects and Y is the number of collision checks that needs to be performed.

As you can see, when the number of items increase, the number of checks to perform increases much more rapidly in the n^2 function than the n*log(n) function.

Here is a table of the mostly used notations:

Notation	Name
O(1)	Constant
O(log n)	Logarithmic
O(n)	Linear
O(n log n)	Linearithmic
O(n^2)	Quadratic

You can find a more complete list in this Wikipedia article.