Notation of Asymptotic Growth

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


Leave a Reply

Your email address will not be published. Required fields are marked *