Question

The time complexity of computing the transitive closure of a binary relation on a set of n elements should be ________

(a) O(n)

(b) O(logn)

(c) O(n^(n+(3/2)))

(d) O(n^3)

The question was asked by my school teacher while I was bunking the class.

I'd like to ask this question from Types of Relations in division Relations of Discrete Mathematics

Answer 1

Correct option is (d) O(n^3)

For explanation I would say: Calculation of transitive closure results into matrix multiplication. We can do matrix multiplication in O(n^3) time. There are better algorithms that do less than cubic time.