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))⟺\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 f $f(n)\in O(g(n))$ but $g(n)\notin O(f(n))$, then $f(n)$ is always faster than $g(n)$.

Common Big-O Functions §

(and where they are found)

• $1$: Running time independent of input.
• $\log (n)$: Typical for “divide and conquer” solutions, for example, lookup in a balanced search tree.
• $n$: Linear. When each input element must be processed once.
• $n\log (n)$: Each input element processed once and processing involves other elements too, for example, sorting.
• $n^2,n^3$: Quadratic, cubic. Processing all pairs (triples) of elements.
• $2^n$: Exponential. Processing all subsets of elements.