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