Chapter 2 introduces the mathematical backgrounds of algorithm analysis.

Order of a Function

The 'Order' of a function describes how fast the function grows. Usually we use three notations to describe it.

• $\Theta$ notation describes the exact order of a function. For example:

  • $f(x)=3x^2=\Theta(x^2)$;
  • $f(x)=3x^2+4x-3=\Theta(x^2)$ , where lower orders will be omitted when they come with items with higher order.

  

  This figure shows the asymptotic relationship between $f(n)$ and $g(n)$ when $f(n)=\Theta(g(n))$

• $O$ notation describes the asymptotic upper bound of a function. For example:

  • $f(x)=4x=O(x)=O(x^2)=\cdots$, in fact, all $x^k$ where $k\geqslant1$ are asymptotic upper bounds of $f(x)$.
  • And it's obvious that $f(x)=3x^2+4x-2=O(x^2)=\Theta(x^2)$. The $\Theta$ notation is stronger than $O$ notation.

  

  This figure shows the asymptotic relationship between $f(n)$ and $g(n)$ when $f(n)=O(g(n))$.

• $\Omega$ notation describes the asymptotic lower bound of a function, just something similar to the $O$ notation.

Besides $\Theta$, $O$ and $\Omega$, there're two another types of notations: $o$ and $\omega$. They are more strict than the upper-case notations, for instance:

• $f(x)=x^2=O(x^2)=O(x^3)$, but $f(x)=o(x^3)\neq o(x^2)$.
• $f(x)=x^4=\Omega(x^4)=\Omega(x^2)$, but $f(x)=\omega(x^2)\neq\omega(x^4)$.

There're the orders of some common functions:

$$ \Theta(1)<\Theta(\lg{n})<\Theta(\sqrt n)<\Theta(n)<\Theta(n\lg n)<\Theta(n^k)<\Theta(k^n)<\Theta(n!) $$

where $k$ is a constant no smaller than 2.

NOTICE: Not all functions have asymptotic bounds.

How to determine the orders' priorities of functions?

• By definition. For instance, $\Theta(g(n))=\{f(n)|\exist c_1, c_2>0, \exist n_0, \forall n>n_0,c_1g(n)\leqslant f(n)\leqslant c_2g(n)\}$. Use this definition to proof.
• L'Hopital's rule.

Order of a Recursive Expression

Recursive expression like $T(n)=3T(\frac{n}{2})+4\Theta(1)$ can have their order calculated by following methods.

Master Theorem (recommended)