Small-O Notation

complexity-theory

Definition

Small-O Notation

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

if grows strictly slower than :

Limit form

If eventually, then

Meaning

Small-o notation gives a strict asymptotic upper bound. Unlike Big-O notation, it does not allow to grow like a constant multiple of .

Thus means that eventually becomes negligible compared with .

Example

Logarithmic growth is strictly below linear growth

because