Make your own free website on Tripod.com

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 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)

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