Computer Science Resources

up one folder

Bachmann–Landau symbols

Bachmann–Landau symbols

It is common for these notations to be written as \(f = \mathcal{O}(g)\), however this is confusing as it then seems as if the notation is symmetric or \(f\) is a function of \(g\). We prefer to use \(f \in \mathcal{O}(g)\) instead.

An overview of the most common Bachmann-Landau symbols:

NOTE: we give \(\Omega\) as used in complexity theory, in number theory another, weaker, definition is common.

A couple of idenities:

Remember, Quicksort has average time complexity \(T(n) \sim 1.39 \, n \log_2 n\)


Content hosted by Evert Provoost