The time complexity of computing the transitive closure of a binary relation…

Answer: O(n^3).

Reason: The standard algorithm for computing the transitive closure of a binary relation given as an n×n adjacency matrix is Warshall's algorithm (a variant of Floyd–Warshall). It uses three nested loops over the vertices and updates reachability using an intermediate vertex.

• Initialize a boolean matrix reachable equal to the adjacency matrix.

• For each vertex k from 1 to n, for each i from 1 to n, and for each j from 1 to n, set reachable[i][j] = reachable[i][j] OR (reachable[i][k] AND reachable[k][j]).

• This triple loop performs Θ(n^3) boolean operations, so the time complexity is Θ(n^3).

Additional note: The output (the full reachability matrix) has Θ(n^2) entries, so any algorithm must take at least Θ(n^2) time to write the result. There are more advanced algorithms based on fast boolean matrix multiplication that can improve the exponent (giving roughly O(n^ω) with ω < 3 in theory), but the standard and expected complexity in most courses and texts is O(n^3).