## 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)$.