Types of Asymptotic Notation
Reading Time: 2 minutes
Theorem: For any two functions \(f(n)\) and \(g(n)\), we have \(f(n) \in \Theta(g(n)) \text{ iff } f(n) \in O(g(n)) \text{ and } f(n) \in \Omega(g(n))\).
Relations between Asymptotic Notations
| Notation | Is Like | Suppose \(f(n) = 0.5n^2 - 2n\), Then |
|---|---|---|
| \(f(n) = O(g(n))\) | \(f(n) ≤ O(g(n))\) | \(f(n) \in O = \{n^2, n^3, n^4, \mathellipsis \} \) |
| \(f(n) = Ω(g(n))\) | \(f(n) ≥ Ω(g(n))\) | \(f(n) \in Ω = \{n^0, n^1, n^2\} \) |
| \(f(n) = Θ(g(n))\) | \(f(n) = Θ(g(n))\) | \(f(n) \in Θ = \{n^2\} \) |
| \(f(n) = o(g(n))\) | \(f(n) < o(g(n))\) | \(f(n) \in o = \{n^3, n^4, \mathellipsis \} \) |
| \(f(n) = ω(g(n))\) | \(f(n) > ω(g(n))\) | \(f(n) \in ω = \{n^0, n^1 \} \) |
Closure Properties of Asymptotic Notations
| Property | Rules |
|---|---|
| Transitivity | $$ \begin{aligned} f(n) &= Θ(g(n)) & \text{ and } \quad g(n) &= Θ(h(n)) & \text { imply } \quad f(n) &= Θ(h(n)) \\ f(n) &= O(g(n)) & \text{ and } \quad g(n) &= O(h(n)) & \text { imply } \quad f(n) &= O(h(n)) \\ f(n) &= Ω(g(n)) & \text{ and } \quad g(n) &= Ω(h(n)) & \text { imply } \quad f(n) &= Ω(h(n)) \\ f(n) &= o(g(n)) & \text{ and } \quad g(n) &= o(h(n)) & \text { imply } \quad f(n) &= o(h(n)) \\ f(n) &= ω(g(n)) & \text{ and } \quad g(n) &= ω(h(n)) & \text { imply } \quad f(n) &= ω(h(n)) \end{aligned} $$ |
| Reflexivity | $$ \begin{aligned} f(n) &= Θ(f(n)) \\ f(n) &= O(f(n)) \\ f(n) &= Ω(f(n)) \end{aligned} $$ |
| Symmetry | $$f(n) = Θ(g(n)) \quad \text{ iff } \quad g(n) = Θ(f(n))$$ |
| Transpose Symmetry | $$ \begin{aligned} f(n) &= O(g(n)) & \text{ iff } \quad g(n) &= Ω(f(n)) \\ f(n) &= o(g(n)) & \text{ iff } \quad g(n) &= ω(f(n)) \end{aligned} $$ |