Intuitive Interpretations of Asymptotic Notations

Definitions

$$\begin{eqnarray*} O(f(n))) & \equiv & \{ g(n) | \exists C > 0, n_0 \in N, \forall n \geq n_0 (g(n) \leq C f(n)) \} \\ \Theta(f(n)) & \equiv & \{ g(n) | \exists C_1,C_2 > 0, n_0 \in N, \forall n \geq n_0 (C_1 f(n) \leq g(n) \leq C_2 f(n)) \} \\ \Omega(f(n)) & \equiv & \{ g(n) | \exists C > 0, n_0 \in N, \forall n \geq n_0 (g(n) \geq C f(n)) \} \\ o(f(n)) & \equiv & O(f(n)) - \Theta(f(n)) \\ \omega(f(n)) & \equiv & \Omega(f(n)) - \Theta(f(n)) \\ \end{eqnarray*}$$

Intuitions

$$\Theta(\cdot)$$ $$=$$
transitivity $$f \in \Theta(g) \;\wedge\; g \in \Theta(h) \Longrightarrow f \in \Theta(h)$$ $$a = b \;\wedge\; b = c \Longrightarrow a = c$$
reflexivity: $$f \in \Theta(f)$$ $$a = a$$
symmetry $$f \in \Theta(g) \Longrightarrow g \in \Theta(f)$$ $$a = b \Longrightarrow b = a$$
$$O(\cdot)$$ $$\leq$$
transitivity $$f \in O(g) \;\wedge\; g \in O(h) \Longrightarrow f \in O(h)$$ $$a \leq b \;\wedge\; b \leq c \Longrightarrow a \leq c$$
reflexivity: $$f \in O(f)$$ $$a \leq a$$
anti-symmetry $$f \in O(g) \;\wedge\; g \in O(f) \Longrightarrow f \in \Theta(g)$$ $$a \leq b \;\wedge\; b \leq a \Longrightarrow a = b$$
$$\Omega(\cdot)$$ $$\geq$$
transitivity $$f \in \Omega(g) \;\wedge\; g \in \Omega(h) \Longrightarrow f \in \Omega(h)$$ $$a \geq b \;\wedge\; b \geq c \Longrightarrow a \geq c$$
reflexivity: $$f \in \Omega(f)$$ $$a \geq a$$
anti-symmetry $$f \in \Omega(g) \;\wedge\; g \in \Omega(f) \Longrightarrow f \in \Theta(g)$$ $$a \geq b \;\wedge\; b \geq a \Longrightarrow a = b$$
$$o(\cdot)$$ <
transitivity $$f \in o(g) \;\wedge\; g \in o(h) \Longrightarrow f \in o(h)$$ $$a < b \;\wedge\; b < c \Longrightarrow a < c$$
$$\omega(\cdot)$$ >
transitivity $$f \in \omega(g) \;\wedge\; g \in \omega(h) \Longrightarrow f \in \omega(h)$$ $$a > b \;\wedge\; b > c \Longrightarrow a > c$$

Q: explain these in intuitive terms: (1) \( \Theta(f) \subseteq O(f) \) and (2) \( \Theta(f) \subseteq \Omega(f) \) Also, \( \Theta(f) = O(f) \cap \Omega(f) \).

Caution: Some functions may not be comparable to each other using asymptotic notations. For example, \( f(n) = n \) and \(g(n) = n^{1+\sin n}\) are not comparable to each other. That is, none of the 5 asymptotic notations applies to their comparison.

Useful Theorems and Proof Techniques

  1. If \(g \in o(f)\) then \(f+g \in \Theta(f)\). Example: \(n^2+5n-4 \in \Theta(n^2)\)
  2. If \(g \in O(f)\) then \(f+g \in \Theta(f)\). Example: \(4 n^2 + n^2 \in \Theta(n^2)\)
  3. If \(c\) is a positive constant, then \(cf \in \Theta(f)\). Example: \(\log(3) n^2 \in \Theta(n^2)\)
  4. \(\log_a f(n) \in \Theta(\log_b f(n))\) for all \(a,b > 1\). Example: \(\log_{10}(n^3-2n+5) \in \Theta(\lg(n^3-2n+5))\)
  5. If \(g_1 \in \Theta(f_1)\) and \(g_2 \in \Theta(f_2)\) then \(g_1 g_2 \in \Theta(f_1 f_2)\) and \(g_1/g_2 \in \Theta(f_1/f_2)\). Example: \((2n^2+5n)(\log(n)+7) \in \Theta(n^2 \log(n))\) and \((2n^2+5n)/(\log(n)+7) \in \Theta(n^2/\log(n))\)
  6. \(\displaystyle \lim_{n \rightarrow \infty} \frac{f}{g} = 0 \Longleftrightarrow f \in o(g)\) Example: \(\log(n) \in o(n)\) and \(n^{999} \in o(1.1^n)\)
  7. \(\displaystyle \lim_{n \rightarrow \infty} \frac{f}{g}\) exists and non-zero \(\Longrightarrow f \in \Theta(g)\) Example: \((n+a)^b \in \Theta(n^b)\)
  8. \(1^k + 2^k + 3^k + \cdots + n^k \in \Theta(n^{k+1})\)
  9. Sterling's Approximation: \(n! = \sqrt{2 \pi n} \left(\frac{n}{e}\right)^n \left( 1 + \Theta\left(\frac{1}{n}\right) \right)\)
  10. If \(f(n) \leq ... \leq ... \leq g(n)\) for sufficiently large n, then \(f \in O(g)\).
  11. If \(f(n) \geq ... \geq ... \geq g(n)\) for sufficiently large n, then \(f \in \Omega(g)\).

Frequently Seen Functions

$$\begin{multline} O(1) \subsetneq \\ O(\log(n)) \subsetneq O(\log^2(n)) ... \subsetneq \\ O(\sqrt[3]{n}) \subsetneq O(\sqrt[3]{n} \log{n}) \subsetneq O(\sqrt[3]{n} \log^2{n}) ... \subsetneq \\ O(\sqrt{n}) \subsetneq O(\sqrt{n} \log{n}) \subsetneq O(\sqrt{n} \log^2{n}) ... \subsetneq \\ O(n) \subsetneq O(n \log(n)) \subsetneq O(n \log^2(n)) ... \subsetneq \\ O(n^2) \subsetneq \\ O(n^3) \subsetneq \\ ... \\ O(1.1^n) \subsetneq \\ O(2^n) \subsetneq \\ ... \\ \end{multline}$$

Master Theorem

Let \(a \geq 1\) and \(b \geq 1\) be constants, let \(f(n)\) be a function, and let \(T(n)\) be defined on the non-negative integers by the recurrence: \[ T(n) = a T(n/b) + f(n) \] Then \(T(n)\) can be bounded asymptotically as follows.

  1. If \(f(n) \in O(n^{\log_b a - \epsilon})\) for some constant \(\epsilon > 0\), then \(T(n) \in \Theta(n^{\log_b a})\).
  2. If \(f(n) \in \Theta(n^{\log_b a})\), then \(T(n) \in \Theta(n^{\log_b a} \lg n)\).
  3. If \(f(n) \in \Omega(n^{\log_b a + \epsilon})\) for some constant \(\epsilon > 0\), then \(T(n) \in \Theta(f(n))\).

See this page for some examples and more explanations.