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'$ ...