The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+20 votes
5.7k views

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

in Set Theory & Algebra by Veteran (52.1k points)
retagged by | 5.7k views

5 Answers

+21 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(n \log n)$
  • (C) $O (n^{1.5})$
by Boss (41.2k points)
edited by
+9
how it "boils down" to matrix multiplication?
+28
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.
0

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?

+1
@reena_kandari

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

Sir I can't understand how the Time complexity is  O(n3). 

0

MRINMOY_HALDER we take boolean product of two matrices to find transitive relation which takes O(n^2). Now for the longest such transitive chain can be be of length n-1. So Taking such boolean product (n-1) times will give us all possible transitive closure. (n-1) (n^2) = O(n^3)

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

by Active (1.8k points)
edited by
+4 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).
by (205 points)
+3 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)
by Loyal (7.6k points)
+2 votes
Option d.
by Active (3.3k points)
Answer:

Related questions

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
50,092 questions
55,255 answers
190,785 comments
86,046 users