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.