Amortized Analysis

Note taker: Shanti Mangala

Lecture # 17

November 4^th, 1998

Amortized Analysis

Amortized Cost: If the time complexity to perform n operations is T(n) in the worst case, then the amortized cost per operation is T(n)/n. This way we get an overall picture of all the operations together, rather than the cost of individual operations, which may vary widely in terms of time complexity.

Advantages:

Illustrates the trade-off between using high time-complexity operations and low time-complexity operations depending on the number of times they are performed in the course of completing the task at hand.

Useful while selecting the appropriate data structure or algorithm to perform a specific task, since amortized analysis gives the overall view, depending on whether the high/low time-complexity features of the data structure/algorithm are used more often.

Examples:

Problem 1: Analysis of stacks: Consider the problem of maintaining a stack and performing n operations such that --

Case 1: Operations performed: PUSH(S, x), POP(S)

Here we can clearly see that --

cost of each operation = 1 Þ cost of n operations = O(n) Þ cost per operation = 1

Case 2: Operations performed: PUSH(S, x), MULTIPOP(S, k)

In this case,

cost of PUSH = 1

cost of MULTIPOP(S, k) = k

using naïve analysis, total cost for n operations = O(n²)

Problem 2: Binary Counter: Now consider the problem of incrementing a binary counter n times, starting from 0.

Operations performed: Increment (A)

sample table with 6 bits:

000000

000001

000010

000011

000010

000011

000100

000101

000110

000111

001000

001001

001010

001011

001100

001101

001110

001111

010000

010001

010010

010011

010100

010101

010110

010111

011000

011001

011010

011011

011100

011101

011110

011111

100000

100001…

Assuming that the counter starts from 0 and using naïve analysis, since the counter can be represented by O(log n) bits, each operation costs O(log n) time. So we can say that

cost of n increments = O(n log n),

Amortized analyses for the above problems:

We now perform a more careful analysis for the above problems.

Accounting Method:

Problem 1: Let us say that every time we perform a PUSH an element, we set aside a cost of 2, one for the PUSH, and one for the POP of the element. At the end of n operations, we can easily see that every item can be PUSHED and POPPED only once, the total cost of all operations, regardless of the type of POP, turns out to be atmost 2n, which means that the amortized cost,

i.e., the cost per operation £ 2.

Problem 2: In this problem, if we look at the table, we can see that the actual number of bits changed is only 1 for every alternate operation, 2 for every 4^th operation, and so on. So, now, taking all these things into consideration, the analysis is:

Total time complexity, O (2n) Þ cost per operation = 2

Potential Method:

This is a very powerful and elegant method for amortized analysis. The first step involves defining an appropriate potential function F . The amortized cost of the i^th operation, a_i = c_i + F (D_i) - F (D_i – 1), where c_i is the actual cost of the i^th operation, which means that the amortized cost is the sum of the real cost and the change in potential.

Hence the total amortized cost is S a_i = F (D_n) - F (D₀) + S c_i, and if F (D_n) ³ F (D₀), then S a_i ³ S c_iwhich means that the total amortized cost is greater than or equal to the total real cost.

Problem 1: If we define the potential function to be the number of elements in the stack, i.e., F (D_i) = |D_i|. Then, the amortized cost for a PUSH is 2,since the real cost is 1, and the amortized cost for a POP is 0, since for the POP operation, the real cost is 1 and the change in potential is -1 since the number of items decreases. With MULTIPOP, the real cost, c_i= k and the change in potential, D F = -k Þ amortized cost = k - k = 0. Thus the amortized cost of each of the operations is O(1).

Problem 2: Defining the potential function, F (Di) = no. of 1's in the current counter Di, the real cost for the i^th increment, c_i = k Þ (k-1) 1's are changed to a 0 and one 0 is changed to a 1,

Then the change in potential, D F = -(k – 1)+1 = -(k - 2)

\ a_i = (k) + (-(k – 2)) = 2

So, again from amortized analysis, we see that the amortized cost of the increments is O(1).

Amortized analysis has thus shown that the cost of n operations for each of the 2 problems considered above is only O(n), which is way better than the naïve analysis performed initially.