###### Question 158 – ISRO-2018

June 1, 2024###### Question 9508 – GATE 2004

June 2, 2024# Question 159 – ISRO-2018

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

Correct Answer: D

Question 76 Explanation:

→ In mathematics the transitive closure of a binary relation R on a set X is defined as the smallest relation on X that contains R and is transitive. More formally, the transitive closure of a binary relation R on a set X is the transitive relation R+ on set X such that R+ contains R and R+ is minimal.

→ For example, if X is a set of airports and x R y means “there is a direct flight from airport x to airport y” (for x and y in X), then the transitive closure of R on X is the relation R+ such that x R+ y means “it is possible to fly from x to y in one or more flights”. Informally, the transitive closure gives you the set of all places you can get to from any starting place.

→ To find the transitive closure of given relation, we can represent the given relation by the graph such that if x R y then there should be directed edge between x and y in a graph.

→ The time complexity of floyd warshall algorithm is O(V3) where V is the number of vertices in the given graph. Take V as the number of elements is set i.e., N.

→ Therefore time complexity for the given question is O(n3).

→ For example, if X is a set of airports and x R y means “there is a direct flight from airport x to airport y” (for x and y in X), then the transitive closure of R on X is the relation R+ such that x R+ y means “it is possible to fly from x to y in one or more flights”. Informally, the transitive closure gives you the set of all places you can get to from any starting place.

→ To find the transitive closure of given relation, we can represent the given relation by the graph such that if x R y then there should be directed edge between x and y in a graph.

→ The time complexity of floyd warshall algorithm is O(V3) where V is the number of vertices in the given graph. Take V as the number of elements is set i.e., N.

→ Therefore time complexity for the given question is O(n3).

O(n)

O(n log n)

O(n

^{3/2})O(n

^{3})
Subscribe

Login

0 Comments