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)$
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 $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
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?
Sir I can't understand how the Time complexity is O(n3).
@ 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 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.
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...
Transitive closure is computed by Floyd -Warshals algorithm, and the time complexity for this is equal to O(n^3) .
I think it’s not Floyd-Warshals algorithm but Roy-Warshall algorithm, pic from Rosen.
64.3k questions
77.9k answers
244k comments
80.0k users