Prove that the worst complexity of Bankers Algorithm is On2m

Prove that the worst complexity of Banker’s Algorithm is O(n²m), where n an m are, respectively, the number of processes and the number of resource types.

Solution

Answer:

Let us take the loop part of the Banker\'s Algorithm : -

for i = 1 to n ---> n times

if(not FINISH[i] )

NEED i < = work then -------> m times

But if you can observe the algorithm , this loop is nested ( repeated loop) ...Loop can run n times in worst case , so it would be = O( n *n *m) = O(n^2 m)