__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.

__Answer:__

Assume that n is
a list of the operations a_{1}, a_{2}, a_{3},… a_{i},…
a_{n. } 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(2^{lgn})

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

O(n)

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

n

__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.

__Answer:__

17.2-2