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
- The potential is always positive, that is $forallcolon i Phi(D_i)ge 0$,
- 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
