The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+16 votes

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

asked in Set Theory & Algebra by Veteran (69k points)
retagged by | 3.1k views

This might help....


5 Answers

+18 votes
Best answer
Answer D

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(Nlogn)$

C) $O (N^{1.5})$
answered by Veteran (49.5k points)
edited by
how it "boils down" to matrix multiplication?
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.

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?


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) in worst case path length to reach farthest vertex could be O(n)...
yes,clear now. :)
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
+5 votes

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

answered by Active (1.5k points)
edited by
+3 votes
warshall algorithim can find transitive closure of any set in O(n3) time. (it basically finds the direct and indirect path from a node to other).
answered by (135 points)
+2 votes
Option d.
answered by Loyal (3.3k points)
+2 votes

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)
answered by Veteran (16.3k points)

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

33,687 questions
40,231 answers
38,803 users