Asymptotic Analysis

All of the definitions of Big-O, Big-Ω, and Big-Θ below have something to do with existentially (∃) bound constants (generally 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} 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} ) 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 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} is asymptotically less than or equal to (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 \preccurlyeq} ) 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 g} if and only if there exists a natural number 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} such that 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) \ge 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}

$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. 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(\log{n})} logarithmic
8. 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(1)} constant

Big Ω

A lower bound on a function 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} :

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 \Omega(n) \rightarrow f(n) \ge Cn \rightarrow f(n) \succcurlyeq n}

Precise Definition: 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)} is big omega of 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 g(n)} if and only if there exists a constant 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} and a natural number 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} such that 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)|} ≥ 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|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 \Omega(g(n)) \longleftrightarrow \exists C \! \in \! \mathbb{R} \ \exists n_0 \! \in \! \mathbb{N} \ \forall n \left( n \ge n_0 \rightarrow |f(n)| \ge C|g(n)| \right)}

Note: 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) = \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.

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)) \longrightarrow \exists \ L<\infty \left( \lim_{n\to\infty}\frac{|f(n)|}{|g(n)|}=L \right)}

Precise Definiton: 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)} is big theta (same order) of 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 g(n)} if and only if there exists constants 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 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 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} such that 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)|} 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}}