in Set Theory & Algebra retagged by
21,837 views
35 votes
35 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)$

in Set Theory & Algebra retagged by
21.8k views

3 Comments

1
1

Thanks you sir, the way you explained the solution was awesome.

0
0
5
5

6 Answers

40 votes
40 votes
Best answer

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

4 Comments

Sir I can't understand how the Time complexity is  O(n3). 

1
1

MRINMOY_HALDER we take boolean product of two matrices to find transitive relation which takes O(n^2). Now for the longest such transitive chain can be be of length n-1. So Taking such boolean product (n-1) times will give us all possible transitive closure. (n-1) (n^2) = O(n^3)

0
0
I do not think that boolean product of two matrices take $O(n^2)$. Rather boolean product of two matrices takes $O(n^3)$ just like usual matrix multiplication, Now if $M$ is the incidence matrix of the relation, then $M^k$ an entry $1$ in those $[i,j]$ cells where there is a path of length $k$. So find transitive closure we find $M^n$ where $n$  is the number of elements in the set $A$ on which the relation is defined. So we need a total of $O(n^4)$ operations in a usual method. But Warshall’s Algorithm uses a dynamic programming approach to reduce this running time to $O(n^3)$.
4
4
13 votes
13 votes

The matrix of transitive closure of a relation on a set of n elements

can be found using n2(2n-1)(n-1) + (n-1)n2 bit operations, which gives the time complexity of O(n4)

But using  Warshall's Algorithm: Transitive Closure we can do it in O(n3) bit  operations

Hence D is the correct answer...

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)

1 comment

I think it’s not Floyd-Warshals algorithm but Roy-Warshall algorithm, pic from Rosen.

 

0
0
Answer:

Related questions