Properties of Asymptotic Notations

In this article, I am going to discuss Properties of Asymptotic Notations. Please read our previous article where we discussed Asymptotic Notations.

Properties of Asymptotic Notations:
As we have gone through the definition of these three notations let’s now discuss some important properties of those notations.

General Properties :
If f(n) is O(g(n)) then a*f(n) is also O(g(n)) ; where a is a constant.

Example: f(n) = 2n²+5 is O(n²)
then 7*f(n) = 7(2n²+5)
= 14n²+35 is also O(n²)

Similarly, this property satisfies both Θ and Ω notation. We can say
If f(n) is Θ(g(n)) then a*f(n) is also Θ(g(n)); where a is a constant.
If f(n) is Ω (g(n)) then a*f(n) is also Ω (g(n)); where a is a constant.

Reflexive Properties:
If f(n) is given then f(n) is O(f(n)). Example: f(n) = n² ; O(n²) i.e O(f(n))

Similarly, this property satisfies both Θ and Ω notation. We can say
If f(n) is given then f(n) is Θ(f(n)).
If f(n) is given then f(n) is Ω (f(n)).

Transitive Properties :
If f(n) is O(g(n)) and g(n) is O(h(n)) then f(n) = O(h(n)).
Example: if f(n) = n , g(n) = n² and h(n)=n³
n is O(n²) and n² is O(n³) then n is O(n³)

Similarly, this property satisfies both Θ and Ω notation. We can say
If f(n) is Θ(g(n)) and g(n) is Θ(h(n)) then f(n) = Θ(h(n)) .
If f(n) is Ω (g(n)) and g(n) is Ω (h(n)) then f(n) = Ω (h(n))

Symmetric Properties :
If f(n) is Θ(g(n)) then g(n) is Θ(f(n)) .
Example: f(n) = n² and g(n) = n² then f(n) = Θ(n²) and g(n) = Θ(n²)
This property only satisfies for Θ notation.

Transpose Symmetric Properties :
If f(n) is O(g(n)) then g(n) is Ω (f(n)).
Example: f(n) = n , g(n) = n² then n is O(n²) and n² is Ω (n)
This property only satisfies for O and Ω notations.

Some More Properties :
1. If f(n) = O(g(n)) and f(n) = Ω(g(n)) then f(n) = Θ(g(n))
2. If f(n) = O(g(n)) and d(n)=O(e(n))
then f(n) + d(n) = O( max( g(n), e(n) ))

Example: f(n) = n i.e O(n)
d(n) = n² i.e O(n²)
then f(n) + d(n) = n + n² i.e O(n²)

3.If f(n)=O(g(n)) and d(n)=O(e(n))
then f(n) * d(n) = O( g(n) * e(n) )

Example: f(n) = n i.e O(n) d(n) = n² i.e O(n²)
then f(n) * d(n) = n * n² = n³ i.e O(n³)

Commonly used Logarithms and Summations:

In the next article, I am going to discuss Master Theorem. Here, in this article, I try to explain the Properties of Asymptotic Notations. I hope you enjoy these Properties of Asymptotic Notations article. I would like to have your feedback. Please post your feedback, question, or comments about this article.

Summary:
I hope this post will be helpful to understand the Properties of Asymptotic Notations
Please share this post with your friends and colleagues.
For any queries please post a comment below.
Happy Coding 😉