Latest revision as of 23:58, 6 December 2015
Orders of Growth
Asymptotic notation: "Big-O"
- Big-O notation gives a way to talk about the rate at which functions grow/decrease
- it allows us to study asymptotic behavior of a function
Big-O can answer:
- what happens when a function becomes very very small?
- very very large?
- how fast the function approaches 0? $\infty$?
Hierarchy of Growth/Decrease
$x \to \infty$
Consider a Limit $\lim\limits_{x \to \infty} \cfrac{x^n}{e^x}$
- who "wins"?
- can apply L'Hopital's Rule several times:
- $\lim\limits_{x \to \infty} \cfrac{x^n}{e^x} = \lim\limits_{x \to \infty} \cfrac{n\, x^{n-1}}{e^x} = \ ... \ = \lim\limits_{x \to \infty} \cfrac{n!}{e^x}$
- $n!$ is a constant (even though it might be big - but it's still a constant)
- so $e^x$ grows faster than any Monomial Function (and any Polynomial Function as well)
We have the following hierarchy of growth:
Let's illustrate it on some monomials:
-
- so we see that higher order monomials grow faster than lower order monomials
Example:
- $\lim\limits_{x \to \infty}\cfrac{3\, x^2 - 2\, x + 1}{6\, x^2 - 5\, x + 4} = \lim\limits_{x \to \infty}\cfrac{x^2\, (3 + \text{smth small})}{x^2\, (6 + \text{smth small})} = \cfrac{3}{6} = \cfrac{1}{2}$
Factorial Growth beats Exponential Growth
- let's show why:
- $\cfrac{x!}{e^x} = \cfrac{x\, (x - 1)\ ... \ 3\, 2\, 1}{e\, e \ ... \ e\, e\, e}$
- almost all terms at the numerator are greater than $e$, only 2 and 1 are smaller
$x \to 0$
It's the opposite for $x \to 0$
- let's consider $x < 1$:
-
- linear function is biggest here!
- so as $x \to 0$, $x^{n+1} < x^n$ - opposite of $x \to \infty$
The hierarchy reverses
Example:
- $\lim\limits_{x \to 0} \cfrac{1 -2x + 3x^2}{4 - 5x + 6x^2} = \cfrac{1}{4}$
- lowest order terms dominate any higher order terms
Summary
- $x \to \infty$: high order terms dominate
- $x \to 0$: low order terms dominate
Big-O Notation
This gives a language for describing the growth
- it has two forms
- one for $x \to \infty$
- another for $x \to 0$
Definition:
- A Function $f$ is in $O(x^n)$ if $|f(x)| < C\, |x^n|$ for some constant $C$
- more generally: $f \in O \big( g(x) \big)$ if $|f(x)| < C\, |g(x)|$ for some $C$
Interpretation:
- we care only about the upper border: "how bad can it be?"
$x \to 0$ | $x \to \infty$ |
$O(x^n)$ consists of all functions $f$ that approach 0 at least as fast as $x^n$ |
$O(x^n)$ consists of all functions $f$ that approach \infty no faster than $x^n$ |
- $\sqrt x \in O(\sqrt x)$
- $x \in O(\sqrt x)$
- $x^2 \in O(\sqrt x)$
|
- $\sqrt x \in O(x^2)$
- $x \in O(x^2)$
- $x^2 \in O(x^2)$
|
$\arctan x = x - O(x^3) = x - \cfrac{x^3}{3} + O(x^5)$
|
$x\, \sqrt{x^2 + 3\, x + 5} = x^2 + O(x) = x^2 + \cfrac{3}{2}\, x + O(1)$
|
Examples
Case $x \to 0$
- $3\, x^2 + 5\, x \in O(x)$, but $\not \in O(x^2)$
- $\sin x \in O(x)$, $\not \in O(x^2)$
- $\ln (1 - x) - x \in O(x^2)$, $\not \in O(x^3)$
- $1 - \cos x^2 \in O(x^4)$, $\not \in O(x^5)$
- $\sqrt{n} \not \in O(x^n) \ \forall n \geqslant 1$ - it goes to zero faster than any other polynomial
- $e^{- 1/x^2} \in O(x^n) \ \forall n$
Case $x \to \infty$
- $\arctan x \in O(1), O(n) \ \forall n \geqslant 1$
- $x\, \sqrt{1 + x^2} \in O(x^2), \ \not \in O(x^{3/2})$
- $\ln (\sinh x) \in O(x), \ \not \in O(\ln x)$: $\ln (\sinh x)$ grows too fast for $\ln x$
- $\cosh x \in O(e^x), \ \not \in O(x^n) \forall n \geqslant 0$
- $\ln x^5 \in O(\ln x), O(x^n) \ \forall n$
Rules of Asymptotic Analysis
- $O(x^m) \cdot O(x^n) = O(x^{m + n})$
- $O(x^m) + O(x^n) = O(x^{\min m, n})$ for $x \to 0$
- $O(x^m) + O(x^n) = O(x^{\max m, n})$ for $x \to \infty$
Examples
Example 1:
- $\cfrac{e^x}{1 - x}$ as $x \to 0$
- $\cfrac{e^x}{1 - x} = e^x\, \cfrac{1}{1-x}$
- have an exponent and a Geometric Series, can Taylor Expand both:
- $e^x\, \cfrac{1}{1-x} = \big(1 + x + O(x^2)\big) \cdot \big(1 + x + O(x^2)\big) = \ ...$
- $... \ = (1 + x)^2 + 2\, (1 + x)\, O(x) + \big( O(x^2)\big)^2 = 1 + 2x + O(x^2) + O(x^3) + O(x^4) = 1 + 2x + O(x^2)$
Applications
- Algorithms: Computational Complexity, Big O
- Error Analysis
- Stirling Formula (see Factorial)
Sources