Aggregate

Analysis:

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.

Example:

Stack

Operations:

In this example, we will

analyze stack with a new operation.

We are using three

functions of stack.

(i) PUSH(S,a)

This function will put an

object or item a onto stack S.

(ii) POP(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.

(iii) MULTIPOP(S,t)

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.

Example:

Top à 45

12

56

99

123 Top à 123

25 25

(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:

MULTIPOP(S, t)

while not STACK-EMPTY(S) and t

> 0

POP(S)

t=t-1