Mumbai University > Information Technology > Sem 3 > Data Structure and Algorithm analysis

Marks: 3 M

Year: Dec 2013, Dec 2012

Following are the properties of asymptotic notations:-

1. Transitive

• If f(n) = Θ(g(n)) and g(n) = Θ(h(n)), then f(n) = Θ(h(n))
• If f(n) = O(g(n)) and g(n) = O(h(n)), then f(n) = O(h(n))
• If f(n) = o(g(n)) and g(n) = o(h(n)), then f(n) = o(h(n))
• If f(n) = Ω(g(n)) and g(n) = Ω(h(n)), then f(n) = Ω(h(n))
• If f(n) = ω(g(n)) and g(n) = ω(h(n)), then f(n) = ω(h(n))

2. Reflexivity

• f(n) = Θ(f(n))
• f(n) = O(f(n))
• f(n) = Ω(f(n))

3. Symmetry

• f(n) = Θ(g(n)) if and only if g(n) = Θ(f(n))

4. Transpose Symmetry

• f(n) = O(g(n)) if and only if g(n) = Ω(f(n))
• f(n) = o(g(n)) if and only if g(n) = ω(f(n))

5. Some other properties of asymptotic notations are as follows:

• If f (n) is O(h(n)) and g(n) is O(h(n)), then f (n) + g(n) is O(h(n)).
• The function loga n is O(logb n) for any positive numbers a and b ≠ 1.
• loga n is O(lg n) for any positive a ≠ 1, where lg n = log2 n.