f(n) can have following notation meaning of g(n) in different ways:
Notation | Bound | Informal Definition: for a large n |
(theta) Θ | UPPER, LOWER | k1 g(n) ≤ f(n) ≤ k2 g(n) for some fixed constants k1 and k2 |
(Big-oh) O | UPPER | |f(n)| ≤ k g(n) for some positive k |
(small-oh) o | UPPER | |f(n)| ≤ k |g(n)|, for EVERY fixed positive number k |
(Big omega) Ω | LOWER | k g(n) ≤ f(n) for some fixed constant k |
(small omega) ω | LOWER | k g(n) ≤ f(n) for EVERY fixed constant k |