Big-O Notation

Tags

comp-sci

An asymptotic function which provides a tight [see page 14, upper] bound. A function \( f(n) \) belongs to the set \( \mathcal{O}(g(n)) \) if it can be shown that there's a constant \( c \) such that the function is always smaller than \( g(n) \) for sufficiently large \( n \).

\begin{align*} \mathcal{O}(g(n)) = \{ f(n) : & \text{\; there exists constants \;} 0 < c \text{\; and \;} n_0 \text{\; such that \;} \\

                            & 0 \leq f(n) \leq cg(n) \text{\\; for all \\;} n \geq n\_0 \\}

\end{align*}