Asymptotic Notations

- Θ notation -

f(n) = Θ(g(n))

There exist positive constants c1, c2, and n0 such that
         
We say g(n) is an asymptotically tight bound for f(n) if f(n) = Θ(g(n)). Informally we can say, as far as time complexity or order of growth, these functions are equal.

---

- O notation -

f(n) = O(g(n))

There exist positive constants c and n₀ such that


We say g(n) is an asymptotic upper bound for f(n) if f(n) = O(g(n)).

---

- Ω notation -

f(n) = Ω(g(n))

There exist positive constants c and n₀ such that
          
We say g(n) is an asymptotic lower bound for f(n) if f(n) = Ω(g(n)).

---

- o notation -

f(n) = o(g(n))

For any positive constant c > 0, there exists a constant
          
We say f(n) is asymptotically smaller than g(n) if f(n) = o(g(n)). We can also express this as the following limit

---

- ω notation -

f(n) = ω(g(n))

For any positive constant c > 0, there exists a constant
          
We say f(n) is asymptotically bigger than g(n) if f(n) = ω(g(n)). We can also express this as the following limit.

---

- Properties -

Transitivity:

  f(n) = Θ(g(n)) and g(n) = Θ(h(n)) ⇒ f(n) = Θ(h(n))
  f(n) = O(g(n)) and g(n) = O(h(n)) ⇒ f(n) = O(h(n))
  f(n) = Ω(g(n)) and g(n) = Ω(h(n)) ⇒ f(n) = Ω(h(n))
  f(n) = o(g(n)) and g(n) = o(h(n)) ⇒ f(n) = o(h(n))
  f(n) = ω(g(n)) and g(n) = ω(h(n)) ⇒ f(n) = ω(h(n))

Reflexivity:

  f(n) = Θ(f(n))
  f(n) = O(f(n))
  f(n) = Ω(f(n))

Symmetry:

Transpose symmetry:

  f(n) = O(g(n)) iff g(n) = Ω(f(n))
  f(n) = o(g(n)) iff g(n) = ω(f(n))

---

- Informal Comparison -

  f(n) = O(g(n)) ≈ a ≤ b
  f(n) = Ω(g(n)) ≈ a ≥ b
  f(n) = Θ(g(n)) ≈ a = b
  f(n) = o(g(n)) ≈ a < b
  f(n) = ω(g(n)) ≈ a > b

---

- Note -

From the definitions of Θ, O, and Ω notations we can conclude the following:

  * For any two functions f(n) and g(n), we have f(n) = Θ(g(n)) iff f(n) = O(g(n)) and f(n) = Ω(g(n)).
  * If f(n) = O(g(n)) then g(n) = Ω(f(n)) and vice versa.