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

recategorized | 890 views
0
It's $O(n^2m)$ -- Banker's algorithm
0
(B )option

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)