36 votes 36 votes The time complexity of computing the transitive closure of a binary relation on a set of $n$ elements is known to be: $O(n)$ $O(n \log n)$ $O \left( n^{\frac{3}{2}} \right)$ $O\left(n^3\right)$ Set Theory & Algebra gatecse-2005 set-theory&algebra normal relations + – Kathleen asked Sep 22, 2014 • retagged Jun 26, 2017 by Silpa Kathleen 24.8k views answer comment Share Follow See all 3 Comments See all 3 3 Comments reply mrinmoyh commented Aug 21, 2019 reply Follow Share https://gatestack.in/t/time-complexity/280 1 votes 1 votes Mr. Amit Kumar commented Sep 9, 2020 reply Follow Share Thanks you sir, the way you explained the solution was awesome. 0 votes 0 votes taran97 commented Oct 1, 2020 reply Follow Share https://www.youtube.com/watch?v=NM0mAmylfMg 7 votes 7 votes Please log in or register to add a comment.
Best answer 43 votes 43 votes 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})$ Akash Kanase answered Nov 28, 2015 • edited Mar 26, 2021 by soujanyareddy13 Akash Kanase comment Share Follow See all 10 Comments See all 10 10 Comments reply Show 7 previous comments tusharp commented Oct 29, 2018 reply Follow Share @ 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) 0 votes 0 votes HitechGa commented Jul 17, 2021 reply Follow Share 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)$. 4 votes 4 votes str commented Oct 9, 2023 reply Follow Share 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. 0 votes 0 votes Please log in or register to add a comment.
14 votes 14 votes The matrix of transitive closure of a relation on a set of n elements can be found using n2(2n-1)(n-1) + (n-1)n2 bit operations, which gives the time complexity of O(n4) But using Warshall's Algorithm: Transitive Closure we can do it in O(n3) bit operations Hence D is the correct answer... Nirmal Gaur answered May 5, 2017 • edited May 5, 2017 by Nirmal Gaur Nirmal Gaur comment Share Follow See all 0 reply Please log in or register to add a comment.
7 votes 7 votes 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). Garima Harsole 14 answered Sep 3, 2017 Garima Harsole 14 comment Share Follow See all 0 reply Please log in or register to add a comment.
6 votes 6 votes 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) Warrior answered Aug 7, 2017 Warrior comment Share Follow See 1 comment See all 1 1 comment reply zxy123 commented Sep 16, 2020 reply Follow Share I think it’s not Floyd-Warshals algorithm but Roy-Warshall algorithm, pic from Rosen. 0 votes 0 votes Please log in or register to add a comment.