# Properties of Asymptotic Notations

## Properties of Asymptotic Notations in Data Structure and Algorithms

In this article, I am going to discuss the Properties of Asymptotic Notations in Data Structure and Algorithms. Please read our previous article where we discussed Asymptotic Notations. As part of this article, we are going to discuss the following Asymptotic Notations Properties.

1. General Properties
2. Reflexive Properties
3. Transitive Properties
4. Symmetric Properties
5. Transpose Symmetric Properties
##### Properties of Asymptotic Notations:

As we have gone through the definition of these three notations (Big-O, Omega-Q, Theta-Î˜) in our previous article. Now letâ€™s 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 for both Î˜ and Î© notation. We can say
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Â³)