# 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}$$ for $$n\geq 4$$.

The definitions of big Oh and related notations are listed below. Let $$f,g$$ be two functions on positive numbers.

• $$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)$$.