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:

  • orders-of-growth.png
  • 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$:
  • orders-of-growth-0.png
  • 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)$

orders-of-growth-ex.png

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