retagged by
24,490 views
36 votes
36 votes

The time complexity of computing the transitive closure of a binary relation on a set of $n$ elements is known to be:

  1. $O(n)$

  2. $O(n \log  n)$

  3. $O \left( n^{\frac{3}{2}} \right)$

  4. $O\left(n^3\right)$

retagged by

6 Answers

Best answer
43 votes
43 votes

Answer $D$

Calculating Transitive Closure boils down to Matrix Multiplication.

We can do Matrix Multiplication in $O(n^{3})$. There are better algo that do less than cubic time, but we can not surely do matrix multiplication in

  • (A) $O(n)$
  • (B) $O(n \log n)$
  • (C) $O (n^{1.5})$
edited by
7 votes
7 votes
warshall algorithim can find transitive closure of any set in O(n3) time. (it basically finds the direct and indirect path from a node to other).
6 votes
6 votes

Transitive closure is computed by Floyd -Warshals algorithm, and the time complexity for this is equal to O(n^3) .

The correct answer is (D) O(n^3)
Answer:

Related questions

24 votes
24 votes
3 answers
4
gatecse asked Sep 21, 2014
7,065 views
The set \(\{1, 2, 4, 7, 8, 11, 13, 14\}\) is a group under multiplication modulo $15$. The inverses of $4$ and $7$ are respectively:$3$ and $13$$2$ and $11$$4$ and $13$$8...