Motivation§

Asymptotic analysis aims to compare a function $f(n)$ with another (simpler) function $g(n)$ that allows us to understand the order of growth of $f(n)$ as $n \to \infty$.

Background§

Limit

Given $f: \mathbb{N}_0 \to \mathbb{R}$, we say

  1. $f$ converges to the limit $L \in \mathbb{R}$ as $n\to\infty$, and write

    $$ \lim_{n\to\infty} f(n) = L, $$

    iff for each $\varepsilon \gt 0$ there exists an $n_{\varepsilon} \in \mathbb{N}_0$ such that

    $$ | f(n) - L | \lt \varepsilon $$

    holds for all $n \geq n_{\varepsilon}$

  2. $f$ tends to $\infty$ as $n\to\infty$, and write

    $$ \lim_{n\to\infty} f(n) = \infty, $$

    iff for each real number $B$ there exists $n_B \in \mathbb{N}_0$ such that $f(n) \gt B$ for all $n \geq n_B$.

Squeeze Theorem

Sps. that $f, g, h : \mathbb{N}_0 \to \mathbb{R}$ such that there exists $n_0 \in \mathbb{N}$ such that for all $n \geq n_0$, the expression

$$ f(n) \leq g(n) \leq h(n) $$

holds, and

$$ \lim_{n\to\infty} f(n) = L = \lim_{n\to\infty} h(n). $$

Then, $\lim_{n\to\infty} g(n)$ exists and is equal to $L$.

Asymptotic Equality§

Asymptotic Equality

Sps. functions $f, g : \mathbb{N} \to \mathbb{R}$, we write $f \sim g$ and say that $f$ is asymptotically equal to $g$ iff

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

Examples§

  1. Let $c \in \mathbb{R}^{+}$, then

    $$ \sqrt{n + c} - \sqrt{n} \sim \frac{c}{2\sqrt{n}}. $$

  2. The $n$th harmonic number is given by $H_n = 1 + \frac{1}{2} + \dots + \frac{1}{n}$ is asymptotically equal to the natural logarithm, i.e.

    $$ H_n \sim \ln n. $$

  3. Another useful asymptotic equality is Stirling’s approximation which gives us

    $$ n! \sim \sqrt{2\pi n}\genfrac{(}{)}{}{}{n}{e}^{n}. $$

Asymptotic Tightness§

Oftentimes, asymptotic equality is too strict so with tightness we consider the growth up to some constant factor and without the need for the existance of a limit.

Asymptotically Tight Bounds

Let $f, g : \mathbb{N}\to\mathbb{R}$, we say that $f$ and $g$ have the same order of growth and write $f \in \Theta(g)$ or $f \asymp g$ iff there exists $c, C \in \mathbb{R}^{+}$ and $n_0 \in \mathbb{N}$ such that

$$ c|g(n)| \leq |f(n)| \leq C|g(n)| $$

holds for all $n \geq n_0$.

Definition by Limit§

Alternatively, if $d$ is a non-zero real number and

$$ d = \lim_{n\to\infty}\frac{|f(n)|}{|g(n)|} $$

exists, then $f \in \Theta(g)$.

Corollary

It then follows that if $f \sim g$, then $f \asymp g$.

Definition by Limit Bounds§

Upper Accumulation Point

Let $f: \mathbb{N} \to \mathbb{R}$, then $u \in \mathbb{R}$ is an upper accumulation point of $f$ iff

  1. For each $\varepsilon \gt 0$, there exists infinitely many natural numbers $n$ such that $f(n) > u - \varepsilon$.
  2. For each $\varepsilon \gt 0$, there exists finitely many natural numbers $n$ such that $f(n) > u + \varepsilon$.

If an upper accumulation point of $f$ exists, then it is unique.

$f$ is bounded above iff there exists $u$ such that $f(n) \leq u$ holds for all $n \in \mathbb{N}$, i.e. if $f$ has an upper accumulation point, then it is bounded above.

Limit Superior

The limit superior is defined as

$$ \limsup_{n\to\infty} f(n) = \begin{cases} +\infty & \text{ if } f \text{ is not bounded above,}\\ u & \text{ if the upper accumulation point } u \text{ for } f \text{ exists,}\\ -\infty & \text{ otherwise. } \end{cases} $$

We then get that $f \in \Theta(g)$ iff

$$ \liminf_{n\to\infty}\frac{|f(n)|}{|g(n)|} \gt 0, \text{ and } \limsup_{n\to\infty}\frac{|f(n)|}{|g(n)|} \lt \infty $$

Asymptotic Upper Bounds§

Asymptotic Upper Bound

Let $f, g : \mathbb{N}\to\mathbb{R}$, we say that $g$ is an asymptotic upper bound for $f$ and write $f \in \mathcal{O}(g)$ iff there exists $C \in \mathbb{R}^{+}$ and $n_0 \in \mathbb{N}$ such that for all $n \geq n_0$,

$$ |f(n)| \leq C|g(n)|. $$

Alternatively, $f \in \mathcal{O}(g)$ iff $$ \limsup_{n\to\infty}\frac{|f(n)|}{|g(n)|} \lt \infty $$

Strict Asymptotic Upper Bounds§

Strict Asymptotic Upper Bound

Let $f, g : \mathbb{N}\to\mathbb{R}$, we say that $g$ is a strict asymptotic upper bound for $f$ and write $f \in o(g)$ iff for every $\varepsilon \in \mathbb{R}^{+}$ there exists $n_{\varepsilon} \in \mathbb{N}$ such that for all $n \geq n_{\varepsilon}$,

$$ |f(n)| \leq \varepsilon|g(n)|. $$

Corollary

It then follows that if $f \in o(g)$, then $f \in \mathcal{O}(g)$.

Definition by Limit§

Let $f, g : \mathbb{N}\to\mathbb{R}$, then $f \in o(g)$ iff

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

Asymptotic Lower Bounds§

Asymptotic Lower Bound

Let $f, g : \mathbb{N}\to\mathbb{R}$, we say that $g$ is an asymptotic lower bound to $f$ and write $f \in \Omega(g)$ iff there eixsts $c \in \mathbb{R}^{+}$ and $n_0 \in \mathbb{N}$ such that for all $n \geq n_0$,

$$ c|g(n)| \leq |f(n)|. $$

Corollary

Sps. $f, g : \mathbb{N}\to\mathbb{R}$, then $f \in \Omega(g) \iff g \in \mathcal{O}(f)$.

Strict Asymptotic Lower Bounds§

Strict Asymptotic Lower Bound

Let $f, g : \mathbb{N}\to\mathbb{R}$, we say that $g$ is a strict asymptotic lower bound for $f$ and write $f \in \omega(g)$ iff for every $\varepsilon \in \mathbb{R}^{+}$ there exists $n_{\varepsilon} \in \mathbb{N}$ such that for all $n \geq n_{\varepsilon}$,

$$ \varepsilon|g(n)| \leq |f(n)| $$

Alternatively, if

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

then $f \in \omega(g)$.