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

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

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 4

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.