In aggregate analysis, we analyze the total execution
time for a sequence of n operations. We will show that, for a sequence of n
operations, it will take T(n) total worst case time. Also In the worst case the
amortized cost will be equal to (total
cost of n operations) / n i.e T(n) /n. In aggregate analysis, all
operations have same amortized cost.
In this example, we will
analyze stack with a new operation.
We are using three
functions of stack.
This function will put an
object or item a onto stack S.
This function will pop an
object or item from top of stack and it will return the popped object.
If POP(S) function will
call on an empty or null stack it will generate an error.
Both of the above operations
have running time equal to O(1).Consider that the cost of each operation is
equal to 1.So the total cost of n PUSH and POP operations is equal to 1 and
therefore execution time for n operations is equal to big theta 1.
This function removes or
pops t number of objects or items from the top of the stack. It will pop all
items from stack if stack have elements or items less than k elements or items.
The top 3 objects will be
popped if we use operation MULTIPOP(S,3).
The value of k should be
positive, if k will negative then MULTIPOP operation will do nothing, no any
change will be occur in stack.
Top à 45
123 Top à 123
(a) (b) (c)
In above example, there is a stack and
45 value is on top shown in (a),the top 4 objects are popped by using
MULTIPOP(S,4) operation and now 123 value is on top shown in (b).The next in
MULTIPOP(S,5) empties the stack in (c) .
In the pseudocode of MULTIPOP
we will use an operation named STACK-EMPTY. STACK-EMPTY operation will
return true if there will be no item in stack, otherwise false.
MULTIPOP operation Pseudocode:
while not STACK-EMPTY(S) and t