# Computer Science Resources

up one folder

Bachmann–Landau symbols
$\newcommand{\abs}[1]{\left\lvert #1 \right\rvert}$

# 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