ISRO CSE 2017 | Question: 80

Question

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

a. $O(n\log n)$

b. $O\left( n^{3/2}\right)$

c. $O( n^3 )$

d. $O(n)$

Comments

Using  Warshall's Algorithm: Transitive Closure we can do it in O(n³) bit  operations

Hence C is the correct answer...

Answer 1

$\begin{bmatrix}
0 & 1 & 1 & 0 & 0 & 1 \\
1 & 0 & 1 & 1 & 0 & 0 \\
0 & 1 & 0 & 1 & 1 & 1 \\
1 & 1 & 1 & 0 & 1 & 0 \\
0 & 1 & 0 & 1 & 0 & 1 \\
1 & 1 & 0 & 1 & 1 & 0 \\
\end{bmatrix}$

If above is a binary relation in it's matrix representation.

Then the following is the $O(V^3)$ Warshall's Algorithm to find the Transitive closure of the underlying graph or binary relation.

for(int via = 0; via < V; via++) {
  for(int start = 0; start < V; start++) {
    for(int end = 0; end < V; end++) {
      matrix[start][end] = matrix[start][end] | ( matrix[start][via] & matrix[via][end] );
    }
  }
}

Answer 2

Option c is the answer

Answer 3

The time complexity of computing the transitive closure is:

3 nested for loops so time complexity is n^3.

Option C