Omega Notation

Tags

comp-sci

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

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

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

\end{align*}