Asymptotic Analysis

All of the definitions of Big-O, Big-Ω, and Big-Θ below have something to do with existentially (∃) bound constants (generally $C$ and $n_0$) that make definition true. These constants are referred to in the discrete mathematics textbook as witnesses.

Definition of Dominance

Also referred to as asymptotic comparison

In general, we say $f$ is asymptotically less than or equal to ($\preccurlyeq$) $g$ if and only if there exists a natural number $n_0$ such that $f(n)\ge g(n)$ for all $n>n_0$

$f\preccurlyeq g⟷\mathrm{\exists }{n}_0\in \mathbb{\mathbb{N}}\mathrm{\forall }n(n\ge n_0\to f(n)\le g(n))$

Conversely, we say $g$ is asymptotically greater than or equal to ($\succcurlyeq$) $f$.

Example

Let $f(n)=5n$ and $g(n)=n^2$:

• When $n<5$, $f(n)>g(n)$
• Asymptotically, $g$ "grows faster" than $f$, so $g(n)$ ≥ $f(n)$ when $n>5$
• Given the definition above, we can say that $5n\preccurlyeq n^2$

Big O

An upper bound on a function $f$:

$f(n)\in O(n)\to f(n)\le Cn\to f(n)\preccurlyeq n$

Precise Definition: $f(n)$ is big oh of $g(n)$ if and only if there exists a constant $C$ and a natural number $n_0$ such that $|f(n)|$ ≤ $C|g(n)|$ for all $n>n_0$ $f(n)\in O(g(n))⟷\mathrm{\exists }C\in \mathbb{ℝ}\mathrm{\exists }{n}_0\in \mathbb{\mathbb{N}}\mathrm{\forall }n(n\ge n_0\to |f(n)|\le C|g(n)|)$

Common Order of Dominance

1. $O(n^n)$ exponential
2. $O(n!)$ factorial
3. $O(n^2)$ polynomial
4. $O(n\log n)$
5. $O(n)$ linear
6. $O(\sqrt{n})$
7. $O(\log n)$ logarithmic
8. $O(1)$ constant

Big Ω

A lower bound on a function $f$ :

$f(n)\in \mathrm{\Omega }(n)\to f(n)\ge Cn\to f(n)\succcurlyeq n$

Precise Definition: $f(n)$ is big omega of $g(n)$ if and only if there exists a constant $C$ and a natural number $n_0$ such that $|f(n)|$ ≥ $C|g(n)|$ for all $n>n_0$ $f(n)\in \mathrm{\Omega }(g(n))⟷\mathrm{\exists }C\in \mathbb{ℝ}\mathrm{\exists }{n}_0\in \mathbb{\mathbb{N}}\mathrm{\forall }n(n\ge n_0\to |f(n)|\ge C|g(n)|)$

Note: $f(n)=\mathrm{\Omega }(g(n))\iff g(n)=O(f(n))$

Big Θ

Means that function has same asymptotic growth as another function up to multiplication by constants. Similar to squeeze theorem in Calculus for proof of convergence.

$f(n)\in \mathrm{\Theta }(g(n))⟶\mathrm{\exists }L<\mathrm{\infty }(\underset{n\to \mathrm{\infty }}{\lim }\frac{|f(n)|}{|g(n)|}=L)$

Precise Definiton: $f(n)$ is big theta (same order) of $g(n)$ if and only if there exists constants $L$ and $U$ and a natural number $n_0$ such that $|f(n)|$ is between$L|g(n)|$ and $U|g(n)|$ for all $n>n_0$. $f(n)\in \mathrm{\Theta }(g(n))⟷\mathrm{\exists }L,U\in \mathbb{ℝ}\mathrm{\exists }{n}_0\in \mathbb{\mathbb{N}}\mathrm{\forall }n(n\ge n_0\to L|g(n)|\le |f(n)|\le U|g(n)|)$

In other words,

$f(n)\in \mathrm{\Theta }(g(n))\leftrightarrow (f(n)\in O(g(n))\wedge f(n)\in \mathrm{\Omega }(g(n)))$

In this case, $n_0$ for Big-Θ takes the larger value of the $n_0$'s used in Big-O and Big-Ω.

Examples

Example 1

• Claim $5n=O\left(n^2\right)$
• Choose witnesses $C=5$ and $n_0=1$ (can be derived mathematically to fit the form of the definition of Big-O: $|5n|\le 5|n^2|$ for all $n\ge 1$)
• $\left\{\begin{array}{ccc}5n& <& 5n^2\\ \left|5n\right|& \le & 5\left|n^2\right|\end{array}\right\}\text{true}\mathrm{\forall }n\ge 1$

Example 2

When Joe implements algorithm A in Java and runs it on his home PC. Running time is

$f_1\left(n\right)=7n+52$

When Sue implements algorithm A in Fortran and runs it on dilbert.cs.tamu.edu, the running time is

$f_2\left(n\right)=2n+25$

Resulting speed of both algorithms is $O\left(n\right)$

Example 3

$\begin{array}{rl}7n^2+6n+2& =O(n^2)\\ n^3-3n+2& =O(n^3)\\ (7n^2+6n+2)(n^3-3n+2)& =O(n^2\cdot n^3)=O\left(n^5\right)\end{array}$

Example 4

(See Wikipedia:Binomial coefficient→)

$\begin{array}{rl}(\genfrac{}{}{0ex}{}{n}{2})& =\frac{n(n-1)}{2}\\ & =\frac{n^2}{2}-\frac{n}{2}\\ & =\frac{n^2}{2}+O\left(n\right)\\ & =O\left(n^2\right)\end{array}$