Banker's algorithm calculated time complexity

algorithm, complexity-theory

Solution

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.

Update: I missed something,

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

Problem

The Banker's algorithm is used to determine if all requests for resources can be satisfied without leading to a deadlock. m is the total number of resources types n is the total number of processes NEED is an array of size m * n, it defines pending requests for each resources type. E.g.: NEEDij = 2 means that process i is requesting for 2 items of resource j. The algorithm is given below: ``` BOOLEAN function SAFESTATE is -- Determines if current state is safe { NOCHANGE : boolean; WORK : array[1..m] of INTEGER = AVAILABLE; FINISH : array[1..n] of boolean = [false, ..,false]; I : integer; repeat NOCHANGE = TRUE; for I = 1 to N do if ((not FINISH[i]) and NEEDi <= WORK) then { WORK = WORK + ALLOCATION_i; FINISH[i] = true; NOCHANGE = false; } until NOCHANGE; return (FINISH == (true, .., true)); } ``` My question is, how is time complexity 0(n * n * m)? More specifically, how does the m term enter the polynomial? Is it because we have to do an element-by-element comparison on a vector of length m?

Original source