Make your own free website on

Exercise 17.1.3:

A sequence of n operations is performed in data structure. The ith operation cost i if i is an exact power of 2, and 1 otherwise. Use aggregate analysis to determine the amortized cost per operation.


Assume that n is a list of the operations a1, a2, a3, ai, an. Where i and n are nonnegative numbers.

Aggregate analysis states that for any value of n, any sequence of n the data structure operations will take a total O(n) worse-case time (upper bound). And the average cost of an operation is O(n)/n. The aggregate analysis we assign the amortized cost of each operation to be the average cost.


In this data structure operation, the total cost is:

T(n) = O(n) + O(2lgn)

T(n) = O(n) + O(n) = O(n)


Then cost per operation is = ------- = O(1)



Exercise 17.2-1:

A sequence of stack operations is performed on a stack whose size never exceeds k. After every k operations, a copy of entire stack is made for backup purposes. Show that the cost of n stack operations, including copying the stack, is O(n) by assigning suitable amortized cost to the various stack operations.