21,837 views

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)$

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

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})$

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

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)

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)$.

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...

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).

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)
by

### 1 comment

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