Back to: Data Structures and Algorithms Tutorials

**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.

**General Properties****Reflexive Properties****Transitive Properties****Symmetric Properties****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)) .

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 this Properties** of Asymptotic Notations in** **Data Structure and Algorithms**article. I would like to have your feedback. Please post your feedback, question, or comments about this article.

**About the Author: Pranaya Rout**

Pranaya Rout has published more than 3,000 articles in his 11-year career. Pranaya Rout has very good experience with Microsoft Technologies, Including C#, VB, ASP.NET MVC, ASP.NET Web API, EF, EF Core, ADO.NET, LINQ, SQL Server, MYSQL, Oracle, ASP.NET Core, Cloud Computing, Microservices, Design Patterns and still learning new technologies.

MichaelThe reflexive property is a fundamental concept in mathematics, particularly in set theory. It states that every element in a set is related to itself. Specifically, a relation \( R \) on a set \( A \) is reflexive if for each element \( a \) in \( A \), the pair \( (a, a) \) is in \( R \). This property ensures that each element is self-related, which is crucial in structures like equivalence relations and order relations. For example, in terms of equality, the reflexive property means that each element is equal to itself, written as \( a = a \).