The Gateway to Computer Science Excellence
+5 votes
890 views

Consider a system which have $‘n’$ number of processes and $‘m’$ number of resource types. The time complexity of the safety algorithm, which checks whether a system is in safe state or not, is of the order of :

  1. $O(mn)$ 
  2. $O(m^{2}n^{2})$
  3. $O(m^{2}n)$
  4. $O(mn^{2})$
in Operating System by Boss (30.2k points)
recategorized by | 890 views
0
It's $O(n^2m)$ -- Banker's algorithm
0
(B )option

2 Answers

+6 votes
Best answer

The below part introduces (n*m) time complexity

for I = 1 to N do // *n times
      if ((not FINISH[i]) and
         NEEDi <= WORK) then // *m times, if it's an array search

but it is also nested in a repeat loop. If that loop can run, in worst case, n times, then the procedure has O(n*n*m) time complexity.

WORK = WORK + ALLOCATION_i; // also O(m) operation, vectors addition

So, the code that executes in the for loop has O(m+m) time complexity.
Of course, O(m+m) = O(m) and the final complexity is O(n*n*m).

by Veteran (102k points)
selected by
+1 vote

In  system of ‘n′ number of processes and ‘m′ number of resource types, complexity of Bankers algorithm will be O( m*n 2 )

NB:

Bankers algorithm cannot allocate resources to multiple processes simultaneously. Resource allocation graph method has complexity of O( n 2) only

by Boss (32.5k points)

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,647 questions
56,479 answers
195,421 comments
100,558 users