The Gateway to Computer Science Excellence

+5 votes

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 :

- $O(mn)$
- $O(m^{2}n^{2})$
- $O(m^{2}n)$
- $O(mn^{2})$

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

52,345 questions

60,503 answers

201,881 comments

95,331 users