Big-O Notation

Big-O notation provides a way to measure the ‘upper limit’ or the ceiling function for the running time (or storage taken) of an algorithm. Mathematically, it is similar to the asymptotic upper bound.

Formal Definition §

Big-O Notation

$$f(n)\in O(g(n))\leftrightarrow \exists n_0,c>0,\forall n>n_0,f(n)\le cg(n)$$

Note

• $f(n),g(n)$ = Growth Function $f(n)$
• $n_0$ = Initial n value for which $g(n)$ (the ceiling function) starts to overtake $f(n)$
• $c$ = Scaling constant for which $g(n)$ can overtake $f(n)$ If the equation holds, $f(n)$ is said to be $O(g(n))$ (‘Big O of’)

Technically, $g(n)$ can be any function. $g(n+1)$, $g(log(n)+n^e)$ and $g(n^2-\log (n))$ are all valid big-O functions, but the closest upper bound is the best option.

This definition has the implication that if $f(n)\in O(g(n))$ but $g(n)\notin O(f(n))$, then $f(n)$ is always faster than $g(n)$.

Examples §