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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle U} and a natural number $n_{0}$ such that $|f(n)|$ is betweenFailed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle L|g(n)|} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle U|g(n)|} for all Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n > n_0} . Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(n) \in \Theta(g(n)) \longleftrightarrow \exists L, U \! \in \! \mathbb{R} \ \exists n_0 \! \in \! \mathbb{N} \ \forall n \left( n \ge n_0 \rightarrow L|g(n)| \le |f(n)| \le U|g(n)| \right)}

In other words,

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n_0} for Big-Θ takes the larger value of the Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n_0} 's used in Big-O and Big-Ω.

Examples

Example 1

• Claim Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 5n=O\left(n^2\right)}
• Choose witnesses Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle C=5} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n_0=1} (can be derived mathematically to fit the form of the definition of Big-O: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |5n| \le 5|n^2|} for all Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n \ge 1} )
• Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{Bmatrix}5n&<&5n^2\\\left|5n\right|&\le&5\left|n^2\right|\end{Bmatrix}\ \mbox{true}\ \forall\ n\ge 1}

Example 2

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

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f_2\left(n\right)=2n+25}

Resulting speed of both algorithms is Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O\left(n\right)}

Example 3

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align}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{align}}

Example 4

(See Wikipedia:Binomial coefficient→)

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} \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{align}}