UGC NET CSE | August 2016 | Part 3 | Question: 50

Question

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 :

• A. $O(mn)$ 
• B. $O(m^{2}n^{2})$
• C. $O(m^{2}n)$
• D. $O(mn^{2})$

Comments

It's $O(n^2m)$ -- Banker's algorithm

---

(B )option

Answer 1

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

Answer 2

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

NB:

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

Answer 3

For n processes and m resources, time complexity of Banker's Algorithm is O(n*n*m).

D is correct.

Answer 4

it is question of  bankers algorithm .

its complexity is O(n²m)

u can c calculation here:

https://stackoverflow.com/questions/1298308/bankers-algorithm-calculated-time-complexity