Time complexity


#1

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


#2

binary relation can be represented as a directed graph.Now for a directed graph transitive closure means we have to find a matrix in which if there is path between two nodes directly or indirectly then there should be one(1) otherwise 0 & all diagonals are always 1’s ,since there is no direct path between node 1 and 2 but still in matrix there is 1 from node 2 to node 1 because there is indirect path from node 2 to 4 then to 1.To find such matrix we use Warshall’s algorithm to find the transitive closure here we start with adjacency matrix with all diagonals matrix as 1
T(0)=(1 0 0 0
0 1 1 1
0 1 1 0
1 0 1 1)
then modify the matrix by checking is there any indirect path between all the pairs of nodes using node 1 as intermediate node .
T(1)=(1 0 0 0
0 1 1 1
0 1 1 0
1 0 1 1)

so Then again modify the matrix by checking is there any indirect path between all the pairs nodes using node 2 as intermediate node . so we keep on doing this to all the nodes we are having here we are going to repeat the process upto n no of times (since n nodes)
To modify one matrix it takes order of O(n^2) time complexity because there are n^2 elements in the matrix . And we are modifying matrix n no of times
so Total time complexity = n * O(n^2)
= O(n^3).

Hope am able to give the answer…