Big-Omega Notation

complexity-theory

Definition

Big-Omega Notation

Let be functions. We say that is Big-Omega of , written

if is eventually at least a constant multiple of :

Meaning

Big-Omega notation gives an asymptotic lower bound. It says that after some finite threshold , the function never grows slower than a constant multiple of .

It is dual to Big-O notation:

Example

Quadratic lower bound

Let

For all ,

Hence with and .