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://www.youtube.com/watch?v=NM0mAmylfMg

---

Transitive closure nikalne ke liye Warshall’s algorithm use hota hai
for k = 1 to n:
  for i = 1 to n:
    for j = 1 to n:
       R[i][j] = R[i][j] OR (R[i][k] AND R[k][j])

• 3 nested loops

• Each runs from 1 to n

• Total operations = n × n × n = n³

Therefore transitive closure = O(n³).

Ye result standard textbook result hai (CLRS, Ullman etc.).

---

We can answer this question by just using common sense,

Every option given $ \in $ $O(n^3)$.

Even if we can find transitive closure in $O(n)$, it will be $O(n^3)$. So $O(n^3)$ is the answer

Answer 1

Answer $D$

Calculating Transitive Closure boils down to Matrix Multiplication.

We can do Matrix Multiplication in $O(n^{3})$. There are better algo that do less than cubic time, but we can not surely do matrix multiplication in

• (A) $O(n)$
• (B) $O(n \log n)$
• (C) $O (n^{1.5})$

Comments

@ MRINMOY_HALDER we take boolean product of two matrices to find transitive relation which takes O(n^2). Now for the longest such transitive chain can be be of length n-1. So Taking such boolean product (n-1) times will give us all possible transitive closure. (n-1) (n^2) = O(n^3)

---

I do not think that boolean product of two matrices take $O(n^2)$. Rather boolean product of two matrices takes $O(n^3)$ just like usual matrix multiplication, Now if $M$ is the incidence matrix of the relation, then $M^k$ an entry $1$ in those $[i,j]$ cells where there is a path of length $k$. So find transitive closure we find $M^n$ where $n$  is the number of elements in the set $A$ on which the relation is defined. So we need a total of $O(n^4)$ operations in a usual method. But Warshall’s Algorithm uses a dynamic programming approach to reduce this running time to $O(n^3)$.

---

I believe transitive closure could be found in O(m+n) = O(n^2) where m is the cardinality of the relation.

Part 1: if relation is antisymetric (its a DAG): then for any vertex v, the vertices v can reach is the union of the vertices neighbours of v can reach. And none of v’s neighbours depend on v. So, standard DFS will work here

Part 2: any general relation is a antisymetric relation of strongly connected components. These components can be found in O(m+n) time and since every element in a strongly connected component can reach every other element, they all have the same set of reachable vertices. So, one can reduce the problem to part 1 and solve.

 

Answer 2

The matrix of transitive closure of a relation on a set of n elements

can be found using n²(2n-1)(n-1) + (n-1)n² bit operations, which gives the time complexity of O(n⁴)

But using  Warshall's Algorithm: Transitive Closure we can do it in O(n³) bit  operations

Hence D is the correct answer...

Answer 3

Transitive closure is computed by Floyd -Warshals algorithm, and the time complexity for this is equal to O(n^3) .

The correct answer is (D) O(n^3)

Comments

I think it’s not Floyd-Warshals algorithm but Roy-Warshall algorithm, pic from Rosen.

 

Answer 4

warshall algorithim can find transitive closure of any set in O(n3) time. (it basically finds the direct and indirect path from a node to other).

Answer 5

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)

Comments

this approach doesnt take into account the problem when adding a new transitive edge would cause new transitive edges needed to be added. Foyd's lgo covers hat by reordering the loop

Answer 6

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

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