- Asymptotic notations and complexity classes
- Intuition
- Properties

We will develop a way to measure the efficiency of algorithms which is *invariant* to the non-essential issues such as the speed of computer hardware and the effiency of the programming language used.

The measurement functions is only sensitive to the *growth* of the time it takes for an algorithm to complete with respect to the size of the input.

- !
- The size of the input is an integer $n$
- We use functions over integers to measure the efficiency of an algorithm.
- $f(n)$ is the
**time**it takes to process input of size $n$ in the*worst case*. - $f$ is monotonic: if $m \leq n$, then $f(m)\leq f(n)$.
- $f$ is strictly positive: $f(n) > 0$ for all $n$.

We want to use functions to measure the inherit *complexity* of *algorithms*.

This is not very straight-forward.

*We don’t care about*:

- !
Runtime environment

- CPU speed
- Start-up time of the program

Implementation issues

- Speed of the language
- Number of statements used
- Overhead in memory data structure

*We do care about*:

- Inherit complexity of the algorithm

Suppose that we have an algorithm $P$. Let’s use some function $f(n)$ to represent the time, in the *worst case*, that $P$ takes to process an input of size $n$.

Let’s look at the effects of various environmental factors on the measure $f(n)$.

$P$ is reimplemented using C (from Python), so it runs 20 times faster now.

$f’(n) = \frac{1}{20} f(n)$

$P$ runs inside a

*docker*image, so it takes an additional 300 ms to start.$f’(n) = f(n) + 300\mathrm{ms}$

But we don’t want to care about these implementation and runtime factors when investigating the complexity of algorithms.

Intuition: given $f(n)$, we define family of (infinite) functions

- !
`$\{g(n): g(n)\ \mathrm{better\ than}\ f(n) \}$`

`$\{g(n): g(n)\ \mathrm{worse\ than}\ f(n) \}$`

`$\{g(n): g(n)\ \mathrm{equivalent\ to}\ f(n) \}$`

We want to define all function which are measure of algorithms which are better than (or same as) $g(n)$.

**Definition**: The Big-O notation

`$$\mathcal{O}(g(n)) = \{f(n) : \exists n_0, c > 0,\forall n > n_0, \ 0 < f(n) < c\cdot g(n)\}$$`

We call $g(n)$ the asymptotic upper bound of the functions in $\mathcal{O}(g(n))$.

If we have an algorithm $A$, and its precise time measurement (on a specific hardware) is given precisely as

`$T(n)$`

, where $n$ is the input size in*bytes*.If

`$T(n)\in\mathcal{O}(g(n))$`

, we are saying that $A$ is**better**than $g(n)$.

*Challenge*:

Check that the variations on the way that the efficiency of $A$ is measured also are in $\mathcal{O}(g(n))$.

$T_1(n)$ is the time that $A$ runs on a slow processor.

$T_2(n)$ is the time that $A$ if the input is measured in the array length.

**Definition**: The $\Omega$-notation

`$$\Omega(g(n)) = \{f(n) : \exists n_0, c > 0,\forall n > n_0, \ 0 < c\cdot g(n) < f(n) \}$$`

We say that $g(n)$ is the asymptotic lower bound of the functions in $\Omega(g(n))$.

**Definition*: The $\Theta$-notation

`$$\Theta(g(n)) = \mathcal{O}(g(n)) \cap \Omega(g(n))$$`

More precisely,

```
$$
\begin{eqnarray}
&& \Theta(g(n)) \\
&=&
\{f(n): \exists n_0, c_1, c_2 > 0,\forall n > n_0,\ 0 \leq c_1\cdot g(n) \leq f(n) \leq c_2\cdot g(n)\}
\end{eqnarray}
$$
```

$\mathcal{O}(g(n))$ is the collection of

**all**the performance measures that are better (or equivalent) to $g(n)$.$\Omega(g(n))$ is the collection of

**all**the performance measures that are worse (or equivalent) to $g(n)$.$\Theta(g(n))$ is the collection of

**all**the performance measures that are equivalent to $g(n)$.

Polynomials:

$$f(n) = \sum_{i=0}^d a_i n^i$$

Exponentials:

$$f(n) = a^n$$

Logorithms

$$f(n) = \log_a(n)$$

Factorials

$$f(n) = n!$$

- !
`$(a^m)^n = a^{mn}$`

`$(a^m) (a^n) = a^{m+n}$`

`$\lim_{n\to\infty} \frac{n^d}{a^n} = 0$`

- !
`$a^{\log_a(n)} = n$`

`$\log_a(mn) = \log_a(m) + \log_a(n)$`

`$\log_a(n^d) = d\cdot \log_a(n)$`

`$\log_b(a) \cdot \log_a(n) = \log_b(n)$`

`$a^{\log_a (n)} = n^{\log_b(a)}$`

Stirling’s approximation:

$$ n! \approx \sqrt{2\pi n} \left(\frac{n}{e}\right)^n $$

For any $a > 1$, $b > 0$ and $c > 1$, we have:

```
$$
\mathcal{O}(\log_a(n)) \subseteq \mathcal{O}(n^b) \subseteq \mathcal{O}(c^n)
$$
```

We can show that:

$$ n! \in\mathcal{O}(n^n) $$

In fact:

$$ \mathcal{O}(2^n) \subset \mathcal{O}(n^n) $$

It’s convenient to treat complexity classes as *variables* in equations.

So, we use the following notations:

- If $f\in \mathcal{O}(g)$, we write it as equality $f=\mathcal{O}(g)$.

If $f = \mathcal{O}(g)$ and $g = \mathcal{O}(h)$, can you prove that $f = \mathcal{O}(h)$?

Does it make sense intuitively?

Does it work out mathematically?

So that $n^2 + 10000= \mathcal{O}(n^3)$.

© KEN PU, 2016