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.