# Big-Omega, Big-Theta and Little-o — Time & Space Complexity (Big-O)

Source: https://www.skillbyai.com/en/big-o/n-theta

> Use Ω, Θ, o and ω to state lower bounds, tight bounds and strict bounds.

## Bounds from below and both sides

**Big-Omega** gives an asymptotic **lower bound**: f(n) = Ω(g(n)) if there exist c > 0 and n₀ with **f(n) ≥ c · g(n)** for all n ≥ n₀. **Big-Theta** gives a **tight bound**: f(n) = Θ(g(n)) if f is both O(g(n)) and Ω(g(n)), meaning f grows at exactly the same rate as g, up to constant factors. So 3n² + 10n is Θ(n²), while it is O(n³) but not Θ(n³). **Little-o** is a strict upper bound: f(n) = o(g(n)) if f grows strictly slower than g (the ratio f/g tends to 0), for example n = o(n²) but n² is not o(n²). **Little-omega** is the strict lower bound. In everyday engineering, people say "Big-O" when they mean a tight bound, as in "merge sort is O(n log n)". In exams and theory, use Θ when you mean tight. Lower bounds also describe problems: **any comparison-based sorting algorithm needs Ω(n log n) comparisons** in the worst case, so merge sort is optimal among comparison sorts.

## Bounds for the same function

f(n) = 4n log n + 3n.

```text
f(n) = 4n log n + 3n

O(n log n)    true  (tight upper bound)
O(n^2)        true  (but loose)
Omega(n)      true  (but loose)
Omega(n log n) true
Theta(n log n) true  (both O and Omega of n log n)
Theta(n^2)    false (not Omega(n^2))
o(n^2)       true  (grows strictly slower than n^2)
o(n log n)    false (grows at the same rate)
```

## Speed limits and minimums

Big-O is a speed limit ("never faster than"), Big-Omega is a minimum speed ("never slower than") and Big-Theta says the car always cruises within a band around one speed.

**Quiz:** What does f(n) = Θ(g(n)) mean?

- [ ] f grows strictly slower than g
- [x] f is both O(g(n)) and Ω(g(n)), so it grows at the same rate as g
- [ ] f is always smaller than g
- [ ] f and g are equal for all n

*Answer:* f is both O(g(n)) and Ω(g(n)), so it grows at the same rate as g. Theta is a tight bound: f is bounded above and below by constant multiples of g.