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
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(n^{2}) time?
Sir I can't understand how the Time complexity is O(n^{3}).
@ 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)
The matrix of transitive closure of a relation on a set of n elements
can be found using n^{2}(2n-1)(n-1) + (n-1)n^{2} bit operations, which gives the time complexity of O(n^{4})
But using Warshall's Algorithm: Transitive Closure we can do it in O(n^{3}) 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) .