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

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 most standard algorithm to compute this is the Floyd-Warshall algorithm, which iteratively updates reachability between all pairs of vertices using an intermediate vertex. This involves three nested loops, each running from 1 to n, resulting in a time complexity of O(n³). While faster algorithms exist for sparse graphs or using matrix multiplication (O(n^2.376)), the general worst-case complexity for dense graphs remains O(n³). Option A (O(n)) and Option B (O(n log n)) are too optimistic as they cannot account for checking all pairs. Option C (O(n^1.5)) is also incorrect as it falls below the cubic bound required for all-pairs reachability in the general case. Thus, O(n³) is the standard accepted complexity.