Recent questions tagged cycle-detection

0 votes

0 answers

OPERATING SYSTEM GALVIN DEADLOCK
In the deadlock chapter, in resource allocation graph algorithm, it is given that detecting a cycle takes O(n^2) operations... But we can find cycle in O(n+m) operations, using DFS. Why they have not considered this.. or if they have considered, what am I missing. Or is it that they have given worst case time assuming #edges(i.e; m)=n(n-1)/2 which would give O(n^2)?

In the deadlock chapter, in resource allocation graph algorithm, it is given that detecting a cycle takes O(n^2) operations... But we can find cycle in O(n+m) operations,...

aambazinga

252 views

aambazinga asked Aug 2, 2018

To see more, click for the full list of questions or popular tags.

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