CODEWITHSUNDEEP
algorithmcomplexity-theory
Natalia
Natalia

Reputation:

Banker's algorithm calculated time complexity

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?

Upvotes: 8

Views: 11166

Answers (1)

Nick Dandoulakis
Nick Dandoulakis

Reputation: 43120

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

Upvotes: 12

Related Questions