Consider a system which have ‘n’ number of processes and ‘m’ number of…
2016
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(m2 n 2)
- C.
O(m2 n)
- D.
O(mn2)
Attempted by 181 students.
Show answer & explanation
Correct answer: D
Answer: O(mn2).
Reason: The safety algorithm (from the Banker's algorithm) may need multiple passes over the list of processes to find a sequence that can finish.
At most n processes become finished overall, so there are at most n successful selections.
To find the next process that can be satisfied, the algorithm may scan up to n processes in a pass.
For each process checked, it compares up to m resource types (Need_i <= Work), costing O(m) per check.
Combining these gives O(number of passes * processes per pass * cost per check) = O(n * n * m) = O(m n2).
Note: With extra bookkeeping one can sometimes avoid rescanning all processes and improve practical performance, but the standard worst-case time for the basic safety check is O(mn2).
A video solution is available for this question — log in and enroll to watch it.