Question

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

• A. $O\left(n\right)$
• B. $O\left(nlogn\right)$
• C. $O\left(n^{3/2}\right)$
• D. $O\left(n^3\right)$

Answer 1

The correct option is D $O\left(n^3\right)$

The time complexity of computing the transitive closure of a binary relation on a set of n elements is O($n^3$). Apply the Warshall's algorithm to compute the transitive closure. The algorithm contains three nested for loops each having frequency n so time complexity is O($n^3$).