Small-Omega Notation

complexity-theory

Definition

Small-Omega Notation

Let be functions. We say that is small-omega of , written

if grows strictly faster than :

Limit form

If eventually, then

Meaning

Small-omega notation gives a strict asymptotic lower bound. Unlike Big-Omega notation, it does not allow to grow like a constant multiple of .

Thus means that eventually dominates by more than any constant factor.

Example

Linear growth is strictly above logarithmic growth

because