Below is the question -

Question

The time complexity of computing the transitive closure of a binary relation on a set of n elements is know to be a -

1) O(n)                          2)  O(nlogn)

3)  O(n^3/2)                           4) O(n³)

Answer 1

Ans : O(n³)

Transitive closure of relation can be represented using directed graph. And in that graph ,using Floyd-Warshall algorithm,one can find out transitivity in  time complexity of O(n³)

Comments

Or you can consider transitive closure to be a form of matrix multiplication, whose order is also O(n^3)