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.7k 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 Aspi R Osa commented Jan 8, 2016 reply Follow Share how it "boils down" to matrix multiplication? 21 votes 21 votes Gate Brahmachari commented Jan 18, 2016 reply Follow Share Transitive closure tells whether there exists a path from node i to node j.Since it is a binary relation means ordered pair consists of two elements. Now represent the graph with Matrix and apply Warshall algorithm. It takes O(n^3) time. 63 votes 63 votes reena_kandari commented Aug 4, 2017 reply Follow Share This problem is similar to finding the reachability matrix of path length 2 for the graph , But In binary relation I think we don't have to multiply matrix n times ,A*A will give us all reachability matrix of length 2.So can we say that we can find Transitive closure of a binary relation in O(n2) time? 0 votes 0 votes joshi_nitish commented Aug 5, 2017 reply Follow Share @reena_kandari what if (a,b),(b,c),(c,d),(d,e),(e,f) is present in relation then (a,f) is also present which has a path length of a---b---c---d---e---f (5).....now in worst case path length to reach farthest vertex could be O(n)... 3 votes 3 votes reena_kandari commented Aug 5, 2017 reply Follow Share yes,clear now. :) 0 votes 0 votes anonymous commented Jan 18, 2018 reply Follow Share Is this solution given in some standard book? If no how did you approach this problem in this way? I mean if we face any new question in exam, what should be the thought process 3 votes 3 votes mrinmoyh commented Oct 1, 2018 reply Follow Share Sir I can't understand how the Time complexity is O(n3). 1 votes 1 votes 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.