Amortized analysis (potential method)

Viewed 58
INSERT(){
   x.value = 2;
   insert X at the beginning of the list 
}
DECREASE(){
   for every X in the list{
      x.value = x.value - 1;
      if(x.value == 0){
          remove X from the list;
      }
   }
}

I need to analyze the pseudocode using the Potential method where ϕ = sum of values in the list.

Analyzing insert for 1 element: A1 = C1 + ϕ1 + ϕ1-1 = 1 (price of adding 1 element) + 2 (1 element with value 2) + 0 (before we added this element we had none therefore the sum is 0) = 3

Analyzing DECREASE after i operations: Ai = Ci + ϕi + ϕi-1 = n (price of 1 operation of DECREASE) + 2 * n (we have n elements with value 2) - (2 * n - 2) (we have 2 * n elements - 2 because we had 1 element less ) = n + 2 Can someone please tell my why i get n + 2, shouldn't the price be the same as when I added 1 element. Thanks in advance sirs.

0 Answers
Related