2. Functions

You will have learned in maths that you can represent the relationship between two variables using graphs, like the one below:

The line on this graph is continuous. This means that, for any value of x, there is a corresponding value of y.

Another way of stating this is using algebra, like so:

$y = f(x)$

Here, 'f' is shorthand for the 'function' that creates the graph.

Big O notation works in a similar way, showing how an algorithm's efficiency (O) changes with the size of the input (n).

This relationship can be linear, or exponential. That is, the efficiency either remains in line with n, expressed as:

$O(n)$

Or the time/space requirements increase as the square of n, expressed as:

$O(n^2)$

Dominant effects

Functions can have multiple parts. For example:

$5n^3 + 2n +3$

One of these parts ($n^3$) will increase much much faster than the rest. This is the dominant effect of the algorithm. When converted to Big O notation, this is the only part that matters, and the rest will be discarded.