Complexity Notation

The notations we use to describe the asymptotic running time of an algorithm are defined in terms of functions whose domains are the set of natural number $N$ , which means we are only analyzing cases where the input size $n \geq 1$ as we are dealing with space and time. Furthermore, since we deal with asymptotic notation we need to discard the constants.

$O (n)$ - Upper limit

Let $f (n) \geq 0, g (n) \geq 0$ be two functions

If there exists a constant $c > 0$ , such that for n sufficiently large, $f (n) \leq c g (n)$

O (g (n)) = {f (n) | \exists c > 0, \exists n_{o} \in N ∋^{'} \forall n \geq n_{o} : f (n) \leq c g (n)}

Basically we are saying that the function $f (n)$ can be even greater than $g (n)$ , but only before reaching the point $n_{o}$ . After that, the function $f (n) \leq c g (n)$ .

$Ω (n)$ - Lower limit

Let $f (n) \geq 0, g (n) \geq 0$ be two functions

O (g (n)) = {f (n) | \exists c > 0, \exists n_{o} \in N ∋^{'} \forall n \geq n_{o} : f (n) \geq c g (n)}

$Θ (n)$

Let $f (n) \geq 0, g (n) \geq 0$ be two functions

O (g (n)) = {f (n) | \exists c_{1} > 0, c_{2} > 0, \exists n_{o} \in N ∋^{'} \forall n \geq n_{o} : c_{1} g (n) \geq f (n) \geq c_{2} g (n)}

f (n) = Θ (g (n)) \leftrightarrow f (n) = O (g (n)) \land Ω (g (n))

$o (n)$

o (g (n)) = {f (n) | \forall c > 0, \exists n_{o} \in N ∋^{'} \forall n \geq n_{o} : f (n) < c g (n)}

$ω (n)$

ω (g (n)) = {f (n) | \forall c > 0, \exists n_{o} \in N ∋^{'} \forall n \geq n_{o} : f (n) > c g (n)}

Hierarchy of notations

$o (g (n)) \subseteq O (g (n))$
$o (g (n)) \cap Ω (g (n)) = \emptyset$
$ω (g (n)) \subseteq Ω (g (n))$
$ω (g (n)) \cap O (g (n)) = \emptyset$

Complexity Notation

$O (n)$ - Upper limit

$Ω (n)$ - Lower limit

$Θ (n)$

$o (n)$

$ω (n)$

Hierarchy of notations

Using summations and limits to define asymptotic complexity

Bounding converging summations

Bounding diverging summations

Comparing limits

Finding the dominant complexity

Complexity Notation ​

O(n) - Upper limit ​

Ω(n) - Lower limit ​

Θ(n) ​

o(n) ​

ω(n) ​

Hierarchy of notations ​

Using summations and limits to define asymptotic complexity ​

Bounding converging summations ​

Bounding diverging summations ​

Comparing limits ​

Finding the dominant complexity ​

Complexity Notation

$O (n)$ - Upper limit

$Ω (n)$ - Lower limit

$Θ (n)$

$o (n)$

$ω (n)$

Hierarchy of notations

Using summations and limits to define asymptotic complexity

Bounding converging summations

Bounding diverging summations

Comparing limits

Finding the dominant complexity