Dark Mode

40 votes

Best answer

@ 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

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

13 votes

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

But using Warshall's Algorithm: Transitive Closure we can do it in **O(n ^{3})** bit operations

Hence **D** is the correct answer...