Questions about amortised analysis

Question

As a preperation of an exam about algorithms and complexity, I am currently solving old exercises. One concept I have already been struggling with when I encountered it for the first time is the concept of amortised analysis. What is amortised analysis and how to do it? In our lecture notes, it is stated that "amortised analysis gives bounds for the "average time" needed for certain operation and it can also give a bound for the worst case". That sounds really useful but when it comes to examples, I have no idea what I have to do and even after having read the sample solution, I have no idea what they are doing.

Let's add up 1 in base 2, i.e. 0, 1, 10, 11, 100, 101, 110, 111, 1000, ... Using amortised analysis, show that in each step only amortised constantly many bits need to be changed.

(the exercise originally is in German, so I apologise for my maybe not perfectly accurate translation)

Now the standard solution first defines $\phi(i) := c \cdot \# \{\text{1-bits in the binary representation}\}$ for some constant $c > 0$. I think this is what is called the potential function which somehow corresponds to the excessive units of time (but I have no idea why I would come up with this particular definition). Assuming that we have to change $m$ bits in the $i$-th step. Such a step always is of the form

$$\dots \underbrace{0 1 \dots 1}_m \to \dots \underbrace{1 0 \dots 0}_m.$$

This statement is understandable to me, however again I fail to see the motivation behind it. Then, out of nowhere, they come up with what they call an "estimate"

$$a(i) = m + c(\phi(i) - \phi(i-1)) = m + c(-m + 2)$$

and they state that for $c=1$, we get $a(i)=2$ which is what we had to show.

What just happened? What is $a(i)$? Why can we choose $c=1$? In general, if I have to show that in each step only amortised constantly many "units of time" are needed, does that mean that I have to show that $a(i)$ is constant?

There are a few other exercises regarding amortised analysis and I don't understand them either. I thought if someone could help me out with this one, I could give the other exercises another try and maybe that'll help me really grasp the concept.

Thanks a lot in advance for any help.

Answer 1

Let $a_i$ be the amortized costs of operation $i$, $c_i$ be the actual costs of operation $i$, and $D_i$ the data structure after operation $i$. The amortized costs of an operation are defined as $$a_i:=c_ i+ \Phi(D_i) -\Phi(D_{i-1}).$$ You usually assume the following

1. The potential is always positive, that is $\forall\colon i \Phi(D_i)\ge 0$,
2. In the beginning the potential is 0, that is $\Phi(D_0)=0$.

These two assumptions are not always necessary but they are commonly used and make the life easier. Now you can consider the potential at costs that have already been paid by previous operations.

To justify this definition consider the accumulated costs of all operations. We get the following telescoping sum $$ \sum_{i=1}^n a_i = \sum_{i=1}^n (c_i +\Phi(D_i) -\Phi(D_{i-1})) = \Phi(D_n) -\Phi(D_{0}) + \sum_{i=1}^n c_i \ge \sum_{i=1}^n c_i. $$ So you see that the sum of the amortized costs exceeds the total actual costs. Hence the amortized costs give an upper bound.

I have not seen the use of the $c$ in your formula. But the $c$ can be simply added to the potential function $\Phi$. So think of the $c$ as a factor that weights the potential, and be redefining the function $\Phi$ you can get rid of it.

So to answer your concrete questions. $a(i)$ denotes the amortized costs for the $i$th operation, that is the actual costs in a sequence of operation charged to operation $i$. The $c$ is some positive factor you can pick. And the $a(i)$s are not constant in general (they are in your example) - you don't have to show anything for the $a(i)$ costs, the values $a(i)$ are the result of your analysis.

Since you seem to speak German, you might also have a look at my German class notes to the potential function.

Answer 2

The potential function method is complicated, your example is simple. The number of bits changed is 1 about half the time, 2 about a quarter of the time, 3 about an eighth of the time, and so on. This is because the number of bits changed, starting from 0, is 1,2,1,3,1,2,1,4 and so on (you get the pattern). So the average number of bits changed is $$ \sum_{k=1}^\infty \frac{k}{2^k} = \sum_{k=1}^\infty \sum_{l=k}^\infty \frac{1}{2^l} = \sum_{k=1}^\infty \frac{1}{2^{k-1}} = 2. $$

Answer 3

Amortized analysis deals with the runtime cost of an operation as an average over a sequence of operations. This is similar to the financial concept of amortization -- a single lump sum, such as a loan, is amortized over a period of time. This fixes a monthly payment for example, even though the principal balance is growing smaller.

In this way, an amortized running time is a type of average, although not the same as an average-case runtime which involves probabilistic analysis on a distribution of inputs.

There are three standard techniques for performing amortized analysis: (1) the aggregate method, (2) the accounting method, and (3) the potential method. This last one is what you are seeing in your lecture notes, and the one A. Schulz is using in his answer. It is also a bit more complicated.

I'd point you to JeffE's excellent lecture notes which include an explanation of all three techniques, starting with the oft-cited example (and the one you encountered) of incrementing a binary counter. It shows that the amortized cost of an increment operation is $O(1)$ when averaged over a sequence of such operations even though the worst-case runtime is $O(\log n)$.

Another resource would be Chapter 17 of [CLRS01], which starts with another common example, a stack with a "multi-pop" operation.

Answer 4

I think the problem statement is clearer when you think of it as a counter that starts at 0 and has an operation that increments the value by one. Every time the counter from your problem is incremented, exactly one bit is flipped on and zero or more bits are flipped off$^*$. The potential function from the example problem is not as out-of-the-blue as you might think. The key to the matter is that only a bit that has previously been turned on can be flipped off. So every time we do an increment operation and turn on a bit, we will store one unit of time in to our "savings account" (the potential function) which we can use for turning that bit off later on.

$^*$This is because when incrementing the counter, you first look at the rightmost bit. If it is off, you turn it on. If it is on, you turn it of and look at the bit one position to the left. If it is off, turn it on and stop. If it is on, turn it off and look at the bit to the left of that bit. So the number of bits you flip in one operation is equal to the position of the first 0-bit from the right.

Initially, both the counter and potential function are 0. After doing one increment operation, the counter is 1 and the potential function is 1 as well. If we increment again, the counter becomes 10. The potential function remains 1. After another step, the counter is 11 and the potential function 2. If we were to increment the counter again, we would need to flip 3 bits to go from 011 to 100. For this we have to use some of the potential and we end up with a new potential of 1. The trick is that the total number of bits actually flipped so far plus the potential function is always equal to two times the number of increment operations. Because the potential function is never negative, the total number of bitflips after $n$ increment operations is at most $2n$, so each operation takes amortized $2$ bitflips.

Another very good example is the array list. Here we have a list (supporting iterating over all the elements and adding a new element) which is implemented by storing the elements in an array. The array initially starts out quite small (say 2 places). When we add an element, it is stored in the array. When we are about to add the 3rd element, there is no more space in the array. To counter this, we create a new array of double the size and copy over all the elements from the original array. This can take a very long time (linear in the number of elements) but amortized analysis shows that each add operation takes only constant time. The array list performs really well in the real world (much better than the linked list). Each operation can be done in constant time, with the caveat that occasionally an operation will take much longer. So these kinds of data structures are not very fit for use in real-time systems but if on occasion you can afford to wait they're very good.