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

The answer is similar in the textbook.

The actual costs of the operations are:

PUSH: cost 1.

POP cost 1.

COPY cost 1.

Let assign the amortized cost for the operation:

PUSH cost 3

POP cost 0.

COPY cost 0.

For every PUSH operation we pay 1 cost for the task and spare 2 credits. These two credits are used to pay off for the POP and the COPY operations. Therefore for the size of the stack s ≤ k we always pay k x 2 thus the amortized cost is always on the upper bound of the actual cost. Since the total amortized cost is O(n).

17.2-2