# Algorithms Notes – Chapter 2

References used for this section: A

Asymptotic Analysis

$\Theta$ – notation

Definition$\Theta (g(n)) = \{ f(n) :$ there exist positive constants $c_{1},c_{2}$ and $n_{0}$ such that $0 \le c_{1}g(n) \leq f(n) \leq c_{2}g(n)$ for all $n \ge n_{0} \}$.

Note on abuse of notation: If a function $f(n)$ satisfies the above condition, it is an element of $\Theta (g(n))$. In standard notation, this should be written as $f(n) \in \Theta (g(n))$… but fuck standard notation, we’re computer scientists. So we choose to abuse the notation by writing it as $f(n) = \Theta (g(n))$. This is useful.

$\mathcal{O}$ – notation

Definition: $\mathcal{O} (g(n)) = \{ f(n):$ there exist positive constants $c$ and $n_{0}$ such that $0 \le f(n) \le cg(n)$ for all $n \ge n_{0} \}$.

We abuse the notation for $\mathcal{O} (g(n))$ the same way as we do for $\Theta (g(n))$ (refer to the note above).

Since $\Theta$ notation is a stronger notion than $\mathcal{O}$ notation, it is evident that $f(n) = \Theta (g(n))$ implies $f(n) = \mathcal{O} (g(n))$. In other words, $\mathcal{O}(g(n)) \subseteq \Theta(g(n))$.

$\Omega$ – notation

Definition: $\Omega(g(n) = \{f(n):$ there exist positive constants $c$ and $n_{0}$ such that $0 \le cg(n) \le f(n)$ for all $n \ge n_{0}\}$.

Once again, we abuse $\Omega$ – notation the same way as the above two.

Theorem: For any two functions $f(n)$ and $g(n)$, we have $f(n) = \Theta(g(n))$ if and only if $f(n) = \mathcal{O}(g(n))$ and $f(n) = \Omega(g(n))$.

This figure kind of summaries the above three notations:

$o$ – notation

Definition: $o(g(n)) = \{f(n):$ for any positive constant $c > 0$ there exists a constant $n_{0} > 0$ such that $0 \le f(n) < cg(n)$ for all $n \ge n_{0}\}$.

This is very similar to $\mathcal{O}$ notation. This example illustrates a key difference:

$2n^2 = \mathcal{O}(n^2)$ and $2n = \mathcal{O}(n^2)$ however, $2n = o(n^2)$ but $2n^2 \not= o(n^2)$. In other words, we use $o$ notation for upper bounds that are not asymptotically tight.

$\omega$ – notation

Definition: $w(g(n)) = \{f(n):$ for any positive constant $c > 0$ there exists a constant $n_{0} > 0$ such that $0 \le cg(n) < f(n)$ for all $n \ge n_{0}\}$.

This is very similar to $\Omega$ notation. This example illustrates a key difference:

$\frac{n^2}{2} = \Omega(n)$ and $\frac{n^2}{2} = \Omega(n^2)$. However, $\frac{n^2}{2} = \omega(n)$ but $\frac{n^2}{2} \not= \omega(n^2)$.  In other words, we use $\omega$ notation for lower bounds that are not asymptotically tight.

Properties

The above defined functions are very similar to real numbers. They also remind me a little of equivalence relations. Refer to Section 3.1 of Introduction to Algorithms 3rd Edition by Cormen et al. for a detailed list of properties of these functions including transitivity, reflexivity etc. along with their real number relational analogs.

xkcd/342