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)\geq g(n)$ for all $n>n_{0}$

$f\preccurlyeq g\longleftrightarrow \exists n_{0}\!\in \!\mathbb {N} \ \forall n\left(n\geq n_{0}\rightarrow f(n)\leq g(n)\right)$

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)\rightarrow f(n)\leq Cn\rightarrow 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))\longleftrightarrow \exists C\!\in \!\mathbb {R} \ \exists n_{0}\!\in \!\mathbb {N} \ \forall n\left(n\geq n_{0}\rightarrow \left|f(n)\right|\leq C\left|g(n)\right|\right)$

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 \Omega (n)\rightarrow f(n)\geq Cn\rightarrow 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 \Omega (g(n))\longleftrightarrow \exists C\!\in \!\mathbb {R} \ \exists n_{0}\!\in \!\mathbb {N} \ \forall n\left(n\geq n_{0}\rightarrow |f(n)|\geq C|g(n)|\right)$

Note: $f(n)=\Omega (g(n))\Leftrightarrow 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 \Theta (g(n))\longrightarrow \exists \ L<\infty \left(\lim _{n\to \infty }{\frac {|f(n)|}{|g(n)|}}=L\right)$

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 \Theta (g(n))\longleftrightarrow \exists L,U\!\in \!\mathbb {R} \ \exists n_{0}\!\in \!\mathbb {N} \ \forall n\left(n\geq n_{0}\rightarrow L|g(n)|\leq |f(n)|\leq U|g(n)|\right)$

In other words,

$f(n)\in \Theta (g(n))\leftrightarrow \left(f(n)\in O(g(n))\wedge f(n)\in \Omega (g(n))\right)$

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|\leq 5|n^{2}|$ for all $n\geq 1$)
• ${\begin{Bmatrix}5n&<&5n^{2}\\\left|5n\right|&\leq &5\left|n^{2}\right|\end{Bmatrix}}\ {\mbox{true}}\ \forall \ n\geq 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{aligned}7n^{2}+6n+2&=O(n^{2})\\n^{3}-3n+2&=O(n^{3})\\\left(7n^{2}+6n+2\right)\left(n^{3}-3n+2\right)&=O\left(n^{2}\cdot n^{3}\right)=O\left(n^{5}\right)\end{aligned}}$

Example 4

(See Wikipedia:Binomial coefficient→)

${\begin{aligned}{\binom {n}{2}}&={\frac {n\left(n-1\right)}{2}}\\&={\frac {n^{2}}{2}}-{\frac {n}{2}}\\&={\frac {n^{2}}{2}}+O\left(n\right)\\&=O\left(n^{2}\right)\end{aligned}}$