Big-O Notation

Given any two functions $f(n)$ and $g(n)$, when we say a function $f(n)$ is $O(g(n))$, we are expressing a certain relationship between the two functions.

Let’s look at the definition, but don’t worry if you don’t grasp it immediately. We’ll expand on its meaning and usage bit by bit.

Definition

We say $f(n)$ is $O(g(n))$ if for some positive constants $c'$ and $n'$,

$$0 \leq f(n) \leq c' \ g(n) \ \ \ \ \ \text{ for all } n \geq n'$$

There are two inequalities above. Let’s take the one on the right first and see what it means.

The inequality on the right

First, let’s focus on the following part of the definition

$$f(n) \leq c' \ g(n) \ \ \ \ \ \text{ for all } n \geq n'$$

for some positive constants $c'$ and $n'$.

On the right-hand side of the inequality, the constant $c'$ is multiplied by $g(n)$. Multiplication of a function by a constant is known as scaling. Scaling has the effect of changing the shape of that function.

Try choosing different values for the constant $c'$ to see how the example function $g(n)$ scales.

Coming back to our inequality, the ...