Gate@Zeal test series

Question

 

Here each resource have a single instance, we can check whether a given system is safe or not is by checking whether there exists a cycle or not, To detect cycle in the graph, the most efficient algorithm is the DFS, So, Time complexity should be O(m+n), assumed number of edges approximately equals to the number of vertices.
But the answer given is O(m*n^2).
Can anyone explain how O(m*n^2)? 

Comments

As per my answer, Time complexity is O(m+n), which is approximately O(m).

But they have given Time complexity is O(m*n^2). Which is approximately O(m^3).

Both are very different, I think they have considered Banker’s algorithm.

---

Yes, I believe they’ve considered the banker’s algorithm. I initially hesitated to contradict the solution because they’d explicitly stated some conditions, and my guess was not the option.

I’m convinced that the question is wrong because of the options, and it explicitly asked for minimum time complexity, but it might do good on your part if you clarify with them.

$O(M)$ is a tighter bound, which I believe to be the correct answer, not because of approximation. Maybe you don’t need to check all the processes, and I was wrong about that in the initial comment.

Processes can request multiple resources, but a resource ultimately can be owned by one process. Maybe we start with a resource and check for cycles till a visited process is encountered again.

---

Yeah, that’s what I am saying.

Answer 1

let suppose the process are

1 2 3 4 5 6 7 8 9…………………………..n

each process required m resource. we know that for getting safe sequence we need to 1 less then total resource so required resources are

process                  (   1           2              3               4                5               6 ………………….n          )

 

resource needed  (  m-1       m-1            m-1          m-1             m-1         m-1 ………………….m-1    )

 

now total resource are  1*(m-1) + 2(m-1)……………….………..n(m-1)

 

for deadlock free  or safe sequence  n(m-1)+1

                                                           nm-n+1

 

hence O(N*M)  time is required

Comments

Each process needs how many resources are not given in the question.

And can you tell me what is wrong with my method?

---

Time Complexity $O(N^2M)$

https://cis.temple.edu/~giorgio/old/cis307f95/readings/deadlock.html