Big Oh Notation
Big Oh notation describes the limiting behavior of a function \(f(n)\) when its argument approaches infinity. Let \(f,g\) be two functions on positive numbers. We write \(f = O(g)\) if there exists \(c>0\) such that \(f(n)\leq c \cdot g(n)\) for sufficiently large \(n\). For example, for \(f(n) = 3n + 4\), we have \(f(n) = O(n)\).
In computer science, big Oh notation is used to characterize the efficiency of an algorithm. The efficiency is measured by the running time, which is the number of basic operations as a function of the input size. For example, the linear search algorithm checks each element in the input one by one, and thus it runs in time \(O(n)\) for inputs of length \(n\).
The following are some representative functions that are commonly used in algorithm analysis.
- Constant: \(f = O(1)\).
- Logarithmic: \(f = O(\log n)\). (binary search)
- Linear: \(f = O(n)\). (linear search)
- Linearithmic: \(f = O(n\log n)\). (merge sort)
- Quadratic: \(f = O(n^2)\). (bubble sort)
- Polynomial: \(f = \hbox{poly}(n) = n^{O(1)}\). There exists \(c\) such that \(f(n)\leq n^c\) for sufficiently large \(n\).
- Exponential: \(f = O(2^n)\).
- Factorial: \(f = O(n!)\).
Note that \(2^n < n! < n^n = 2^{n\log n}[/latex] for [latex]n\geq 4[/latex]. The definitions of big Oh and related notations are listed below. Let [latex]f,g[/latex] be two functions on positive numbers.
- [latex]f = O(g)\), if there exists \(c>0\) such that \(f(n)\leq c \cdot g(n)\) for sufficiently large \(n\).
- \(f = \Omega(g)\), if there exists \(c>0\) such that \(f(n)\geq c \cdot g(n)\) for sufficiently large \(n\).
- \(f = o(g)\), if for all \(c >0\) such that \(f(n)\leq c\cdot g(n)\) for sufficiently large \(n\).
- \(f = \omega(g)\), if for all \(c>0\) such that \(f(n)\geq c\cdot g(n)\) for sufficiently large \(n\).
- \(f = \Theta(g)\), if there exists \(c, d>0\) such that \(f(n)\geq c \cdot g(n)\) and \(f(n)\leq d \cdot g(n)\) for sufficiently large \(n\).
The relationship between these notations are as below.
- \(f = O(g)\) if and only if \(g=\Omega(f)\).
- \(f = o(g)\) if and only if \(g=\omega(f)\).
- \(f = \Theta(g)\) if and only if \(f = O(g)\) and \(g=\Omega(f)\).