Asymptotic Analysis

Overview

The most commonly used method for analyzing order of growth is asymptotic analysis. Here resources of an algorithm are measured by some function whose leading coefficients and lower-ordered terms are ignored.

Asymptotically Tight

Θ-notation

$Θ$ -notation refers to a strict lower- and upper-bound. It is defined as set

Θ (g (n)) = {f (n) ∣ \exists c_{1}, c_{2}, n_{0} > 0, \forall n \geq n_{0}, 0 \leq c_{1} g (x) \leq f (n) \leq c_{2} g (n)} .

$O$ -notation

$O$ -notation refers to a strict upper-bound. It is defined as set

O (g (n)) = {f (n) ∣ \exists c, n_{0} > 0, \forall n \geq n_{0}, 0 \leq f (n) \leq c g (n)} .

Ω-notation

$Ω$ -notation refers to a strict lower-bound. It is defined as set

Ω (g (n)) = {f (n) ∣ \exists c, n_{0} > 0, \forall n \geq n_{0}, 0 \leq c g (n) \leq f (n)} .

Asymptotically Loose

$o$ -notation

$o$ -notation refers to an upper bound that is not asymptotically tight. It is defined as set

o (g (n)) = {f (n) ∣ \forall c > 0, \exists n_{0} > 0, \forall n \geq n_{0}, 0 \leq f (n) < c g (n)} .

Alternatively, we can express $o$ -notation using limits. If $f (n) = o (g (n))$ , then

lim_{n \to \infty} \frac{f (n)}{g (n)} = 0.

ω-notation

$ω$ -notation refers to a lower bound that is not asymptotically tight. It is defined as set

ω (g (n)) = {f (n) ∣ \forall c > 0, \exists n_{0} > 0, \forall n \geq n_{0}, 0 \leq c g (n) < f (n)} .

Alternatively, we can express $ω$ -notation using limits. If $f (n) = ω (g (n))$ , then

lim_{n \to \infty} \frac{f (n)}{g (n)} = \infty .

Arithmetic

When encountering equations with asymptotic notation on both sides of the equality, we interpret the equation using the following rule:

No matter how the anonymous functions are chosen on the left of the equal sign, there is a way to choose the anonymous functions on the right of the equal sign to make the equation valid.

For example, $2 n^{2} + Θ (n) = Θ (n^{2})$ states that for all $f (n) \in Θ (n)$ , there exists some $g (n) \in Θ (n^{2})$ such that $2 n^{2} + f (n) = g (n)$ .