Data Structures Analysis: Aggregate and Amortized Analysis Homework

This document presents a solution to a homework assignment focusing on aggregate and amortized analysis techniques applied to data structures. The solution analyzes the time complexity of stack operations (PUSH, POP, MULTIPOP) and demonstrates how to derive an average cost of O(1) per operation using aggregate analysis. It provides a concrete example with a stack of elements and illustrates the difference between actual and amortized time. The solution further examines the incrementing of a binary number, determining an amortized time of O(1) per increment. Finally, it addresses the insertion operation in a binomial heap, utilizing amortized analysis to prove that the time for n insertions is O(n). This resource is available on Desklib, a platform offering AI-powered study tools.

Answer 1: Summery of Aggregate analysis
Aggregate analysis can be used to derive average, or amortized cost per operation, for sequence of n
operation by dividing worst case cost by number of operation i.e. T(n)/n here.
Analysis of Stack operations
There are two core operations on stack, PUSH (STK, I) which add a element I on stack STK and
POP(STK) which returns a top element from stack STK, both takes O(1) time. We can add a operation
that can do multiple pop, MULTIPOP (STK, k), which do minimum (n, k) pop in sequence in O(n)
times(n is number of elements on stack ).
In aggregate analysis, any sequence of n PUSH, POP, MULTIPOP (STK, k) operation will take O (1)
time per operation. How? For n PUSH at any instance will take n*O (n) time for all push operations
and for per push operation time divide it by n, it comes O (1) time per Push operation. For n POP
operation at any instance will take n*O (n) for all POP operations and for time per POP operation
divide it by n, it comes O(1) time per Pop operation. And for the time of MULTIPOP operation, it will
pop only equal to number of time push done, because each element will be pushed and popped
once. Thus it is O (n)/n = O (1).
So this analysis derives that average cost of any stack operation is O (1).
Let’s calculate actual and amortized time for stack operation by taking example. As it is stated in first
paragraph amortized time is worst case average time, so actual time must be equal to or less than
amortized time. Let’s push 9 elements in empty stack and then perform some multipop operation.
23
23
34
12
2
4 4
9 9
7 7
6 6 6
------- -------- -------- -------- ---------
a b c d e
Figure 1The empty stack shown in (a). The action of 9 pushes on a stack S, shown in (b). The top 5
objects are popped by MULTIPOP(S, 5), whose result is shown in (c). The top 3 objects are popped by
MULTIPOP(S, 3), whose result is shown in (d). The next operation is MULTIPOP(S, 4), which empties
the stack—shown in (e)—since there were fewer than 4 objects remaining.
As shown in figure 1,
1. Each push will take O (1) time so, for 9 push it is O(9) for push operation.

2. First multipop takes 0(5), second takes O(3) and third will take O(1) (min of 1,4)
3. So actual time is equals to O (18)/18 operations so it is O(1). Similarly amortized time is same
as actual time.
Analysis of incrementing a binary number
By observing algorithm given in textbook, there is 16 bit counter. To increase it we require adding
one to it. It will start adding it from least significant bit (LSB), if carry is generated will be added to
next higher order bit. Observing the bit toggling b0 will be toggled in every increment that is n time.
Bit b1 will be toggled in every alternate increment that is n/2 time. In general ith bit will be toggled
n/2i time for all increments. So by summing all up it is 2n that is O (n) time, for n increments. So
amortized time for incrementing a binary number operation is O (n)/n=O (1) per increment.
Answer 2: Derivation of time [O (1)] for insertion in of binomial heap by amortized analysis
Binomial heap is base on priority queue. Priority queue can be implemented using array or link list.
Similarly binomial tree can be implemented. Here if we observe algorithm for insertion then it is
nothing but create a binomial tree of one node and then do union with existing binomial tree.
Worst case cost of creating a binomial tree is O (1). But to do union takes time O(log n) now if we do
not consider amortized analysis it is O(nlogn) for n insertion. But by using amortized analysis we can
see each case in union and prove something different.
For example, for doing union of single node binomial tree with single or two nodes it is log1 and log2
respectively that is o (1) then for every alternate next it may be doubled. So by summing all cost of
all n operation it will be 1+1+2+2+3…..logn And so on. So by simplifying we can say it is 2(1+2+3+…
logn). By taking loose bound we can say it 2n as n>logn. So its comes O(n). Hence amortized analysis
can be used to prove that time for n insertion in binomial heap is O(n).