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

retagged | 6k views
0

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})$
by Boss (41.5k points)
edited
+10
how it "boils down" to matrix multiplication?
+31
Transitive closure tells whether there exists a path from node i to node j.Since it is a binary relation means ordered pair consists of two elements. Now represent the graph with Matrix and apply Warshall algorithm. It takes O(n^3) time.
0

This problem is similar to finding the reachability matrix of path length 2 for the graph , But In binary relation I think we don't have to multiply matrix n times ,A*A will give us all reachability matrix of length 2.So can we say that we can find Transitive closure of a binary relation in O(n2) time?

+1
@reena_kandari

what if (a,b),(b,c),(c,d),(d,e),(e,f) is present in relation then (a,f) is also present which has a path length of

a---b---c---d---e---f (5).....now in worst case path length to reach farthest vertex could be O(n)...
0
yes,clear now. :)
0
Is this solution given in some standard book? If no how did you approach this problem in this way? I mean if we face any new question in exam, what should be the thought process
0

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

0

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)

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

by Active (2.1k points)
edited

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 Loyal (7.8k points)