Please enable JavaScript.
Coggle requires JavaScript to display documents.
ASYMTOTIC NOTATIONS AND ITS PROPERTIES - Coggle Diagram
ASYMTOTIC NOTATIONS AND ITS PROPERTIES
Three Notations
Big-O notation
Omega notation
Theta notation
Properties
Symmetry:
f(n) = Θ(g(n)) if and only if g(n) = Θ(f(n))
Example: If f(n) = n2 and g(n) = n2 then f(n) = Θ(n2) and g(n) = Θ(n2)
Transistivity:
f(n) = O(g(n)) and g(n) = O(h(n)) ⇒ f(n) = O(h(n))
Example: If f(n) = n, g(n) = n2 and h(n) = n3 ⇒ n is O(n2) and n2 is O(n3) then n is O(
Reflexivity: If f(n) is given then
f(n) = O(f(n))
Example: If f(n) = n3 ⇒ O(n3)
Observations:
max(f(n), g(n)) = Θ(f(n) + g(n))
Transpose Symmetry:
f(n) = O(g(n)) if and only if g(n) = Ω(f(n))
