When expressing the Computational complexity of algorithms, *big O notation* is used to classify their behaviour as the size of inputs tends towards some particular value or infinity.

Formally \(f\) may be said to be \(O(g)\), or \(f(n) = O(g(n))\) as \(n \to \infty\) when
\[
|f(n)| \leq c \cdot g(n) \quad \forall n \ge k
\]
where \(c\) and \(k\) are called the *witnesses* to the relation.

As a concrete example, consider \(3n^{2} + 4n = O(n^2)\). As \(n \le n^2\) for all \(n \ge 1\), we may infer that \(3n^{2} + 4n \le 3n^{2} + 4n^{2}\), which implies \(3n^{2} + 4n \le 7n^{2}\). This shows the relations to hold for witness of \(c = 7\) and \(k = 1\).

Notation | Term |
---|---|

\(O(1)\) | constant |

\(O(\log \log n)\) | double logarithmic |

\(O(\log n)\) | logarithmic |

\(O(n^{c}) \text{ where } 0<c<1\) | fractional power |

\(O(n)\) | linear |

\(O(n \log n)\) | linearithmic |

\(O(n^2)\) | quadtratic |

\(O(n^c)\) | polynomial |

\(O(c^{n}) \text{ where } c>1\) | exponential |

\(O(n!)\) | factorial |

While \(O(g)\) is used to denote \(f \leq g\) other common symbolism exists for similar relations.

Notation | Comparison | Limit Definition |
---|---|---|

\(f = o(g)\) | \(f < g\) | \(\lim_{x \to \infty} \frac{f(x)}{g(x)} = 0\) |

\(f = O(g)\) | \(f \le g\) | \(\lim_{x \to \infty} \frac{f(x)}{g(x)} < \infty\) |

\(f = \Theta(g)\) | \(f = g\) | \(\lim_{x \to \infty} \frac{f(x)}{g(x)} \in \mathbb R_{>0}\) |

\(f = \Omega(g)\) | \(f \ge g\) | \(\lim_{x \to \infty} \frac{f(x)}{g(x)} > 0\) |

\(f = \omega(g)\) | \(f > g\) | \(\lim_{x \to \infty} \frac{f(x)}{g(x)} = \infty\) |