GATE CSE 2005 | Question: 7

Question

The time complexity of computing the transitive closure of a binary relation on a set of $n$ elements is known to be:

• A. $O(n)$

• B. $O(n \log  n)$

• C. $O \left( n^{\frac{3}{2}} \right)$

• D. $O\left(n^3\right)$

Comments

https://gatestack.in/t/time-complexity/280

---

Thanks you sir, the way you explained the solution was awesome.

---

https://www.youtube.com/watch?v=NM0mAmylfMg

Answer 1

Here is a more intuitive way you can understand. :)

1. For a set of n elements there are O(n^2) tuples in a relation.

2. To check the transitive completeness of one tuple E.g., (a,b) in the array, we first need to find if (a,b)'s transitive pair is present i.e (b,1), (b,2) ... (b, n) in this array (which is O(n) in worst case).

3. After we find the corresponding pairs, we check if the transitive closure of each pair that was found is present. (This is only take O(1) as it is a simple check and add condition). Therefore the time taken to complete the transitive closure of one tuple is O(n).

4. To do this for all elements in the array it is O(n^2) * O(n) which is O(n^3)

Answer 2

Answer will be (D) we use warshall's algorithm to compute the transitive closure 

source : https://www.geeksforgeeks.org/transitive-closure-of-a-graph/