ISRO2018-56

Question

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

1. $O(n)$
2. $O(n*\log(n))$
3. $O(n^{\frac{3}{2}})$
4. $O(n^{3})$

Comments

option D is correct.

Answer 1

The matrix of the 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.

Answer 2

Option D:- using Floyd warshall algorithm we can find transitive closure

Answer 3

Answer is(D).

Comments

Please provide an explanation.

Answer 4

ANSWER: D    O( n³ )

Transitive closure of a graph

Given a directed graph, find out if a vertex j is reachable from another vertex I for all vertex pairs (i, j) in the given graph. Here reachable means that there is a path from vertex I to j. The reach-ability matrix is called transitive closure of a graph.

            

Transitive closure of above graphs is 
     1 1 1 1 
     1 1 1 1 
     1 1 1 1 
     0 0 0 1 

Floyd Warshall Algorithm can be used, we can calculate the distance matrix dist[V][V] using Floyd Warshall, if dist[i][j] is infinite, then j is not reachable from i, otherwise j is reachable and value of dist[i][j] will be less than V.

Time Complexity: O(V³) where V is the number of vertices in the given graph.

source: geeksforgeeks