Big Omega
A lower bound. The cost is at least a constant times the reference for large n.
Complexity in Numbers: 3n + 5 is Theta(n)
n = 1: f = 8, between n = 1 and 4n = 4? The lower bound holds, 8 >= 1. The upper bound fails, 8 > 4: the constant 5 still dominates. Big O only promises the bound for large n.
Cost
- Space
- O(1)
Before this
Taught by the same lesson
Complexity in Numbers covers these too, in the same run.