CMSC351

Asymptotic Theory⌗

Big Notation⌗

Big-O⌗

We say \(f(x) = \mathcal{O}(g(x))\) if \(\exists x_{0}, C > 0\) such that \(\forall x \ge x_{0}, f(x) \le Cg(x)\)

Big-Omega⌗

We say \(f(x) = \Omega(g(x))\) if \(\exists x_{0}, D > 0\) such that \(\forall x \ge x_{0}, f(x) \ge Dg(x)\)

Big-Theta⌗

We say \(f(x) = \Theta(g(x))\) if \(\exists x_{0}, C, D > 0\) such that \(\forall x \ge x_{0}, Bg(x) \le f(x) \le Cg(x)\)

Caveats⌗

• \(f(x) = \mathcal{O}(g(x))\) does not imply \(g(x) = \Omega(f(x))\)
• It may not be intuitive, but there are functions that are not \(\Theta()\) of something, mostly non-polynomials
  • \(f(x) = x^{2}sin(x)\) is \(\mathcal{O}(x^{2})\) but not \(\Omega(x^{2})\)
• When doing big notation, we are interested in the most-limiting bounding function, that is basically everything is \(\mathcal{O}(x!)\), but that’s not very helpful

Orders of Magnitude⌗

1. \(1\)
2. \(\log x\)
3. \(x\)
4. \(x \log x\)
5. \(x^{2}\)
6. \(x^{2}\log x\)

Limit Theorem⌗

If \(\lim_{n \rightarrow \infty} f(n)\) and \(\lim_{n \rightarrow \infty} g(n)\) exist:

1. If \(\lim_{n \rightarrow \infty}\frac{f(n)}{g(n)} = r\) where \(r\) is some non-zero real number, then \(f(n) = \Theta(g(n))\)
2. If \(\lim_{n \rightarrow \infty}\frac{f(n)}{g(n)} = 0\), then \(f(n) = \mathcal{O}(g(n))\)
3. If \(\lim_{n \rightarrow \infty}\frac{f(n)}{g(n)} = \infty\), then \(f(n) = \Omega(g(n))\)

Master Theorem⌗

Suppose \(T(n)\) satisfies the recurrence relation \(T(n) = aT(\frac{n}{b}) + f(n)\).

1. If \(f(n) = \mathcal{O}(n^{c})\) and \(\log_{b}a > c\), then \(T(n) = \Theta(n^{\log_{b}a})\)
2. If \(f(n) = \Theta(n^{c})\) and \(\log_{b}a = c\), then \(T(n) = \Theta(n^{\log_{b}a}\lg n)\)
   1. If \(f(n) = \Theta(n^{c}\lg^{k}n)\) and \(\log_{b}a = c\), then \(T(n) = \Theta(n^{\log_{b}a}\lg^{k+1} n)\)
3. If \(f(n) = \Omega(n^{c})\) and \(\log_{b}a < c\), then \(T(n) = \Theta(f(n))\)

Time Complexities⌗