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

A. ...

Question

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

A. O(n)
B. O(n log n)
C. O(n^(3/2))
D. O(n^3)

Accepted Answer

D. O(n^3) The transitive closure of a relation on n elements can be computed using the Floyd-Warshall algorithm, which runs in O(n^3) time. It iterates over all triples (i, k, j) checking whether a path from i to j exists via intermediate vertex k. No known algorithm does better than O(n^3) for general dense relations using standard RAM models.

The time complexity of computing the transitive closure of a binary relation on a set of n elements is known to be: A. O(n) B. O(n log n) C. O(n^(3/2)) D. O(n^3)