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

The transitive closure of a binary relation on n elements represents all pairs (a, b) such that there is a path from a to b in the relation graph. The standard algorithm for computing this is the Floyd-Warshall algorithm, which iteratively updates reachability between all pairs of vertices. This involves three nested loops iterating over n elements, resulting in a time complexity of O(n³). While faster algorithms exist for sparse graphs (like using BFS/DFS from each node), the general worst-case bound for dense relations is cubic. Option A (O(n log n)) and Option D (O(n)) are too optimistic for this problem, as they represent complexities typical of sorting or simple traversal. Option B (O(n^(3/2))) is not a standard complexity for transitive closure. Thus, O(n³) is the accepted answer.