[Solved]: Questions about amortised analysis

Problem Detail: 

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.

Asked By : Huy

Answered By : A.Schulz

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/9021