1
$\begingroup$

With reference to chapter 17 of CLRS, (Amortized analysis). I'm trying to understand the differences between the accounting method and the potential method.

Let's start with standard analysis of the stack, three operations supported namely $\text{push}(x), \text{pop}(),\text{multipop}(k)$ the cost of this operations is respectively $O(1),O(1),O(\min(k,n))$, where in the latter $n$ is the size of the stack.

Standard complexity analysis of a sequence of operations $o_1,\ldots,o_n$ where for all $i$ $o_i \in \left\{ \text{push},\text{pop},\text{multipop}\right\}$ would lead to $O(n)$ as worst case. The reason of this is because whatever in the worst case the stack will have $n$ elements, and the worst case of $\text{multipop}$ will cost $O(n)$, hence we have the worst case. amortized cost will be $O(n)/n = O(1)$.

For the accounting method we will assign an amortized cost to each operation. If $o_1,\ldots,o_n$ are the operations above with costs $c_1,\ldots,c_n$ (real amortized cost) we assign amortized cost $\hat{c}_i$

$$ \hat{c}_i = \left\{ \begin{array}{ll} 2 & \text{if $o_i$ = push} \\ 0 & \text{otherwise} \end{array} \right. $$

Which means whenever we push an element $x$ in the stack we double it's cost due to the potential cal of $\text{pop}$ or the $i$-th iteration of $\text{multipop}$. Because of this we have the inequality

$$ T(n) = \sum_{i=1}^{n} c_i \leq \sum_{i=1}^{n} \hat{c}_i \leq 2n \Rightarrow T(n) = O(n). $$

If we use the potential method instead we define $D_i$ the status of the data structure at iteration after executing $o_i$, and we define $\Phi(D_i)$ as the size of the stack after executing $o_i$.

By definition of the potential cost we will have

$$ \hat{c}_i = c_i + \Phi(D_i) - \Phi(D_{i-1}) $$

Three cases are distinguished

$$ \hat{c}_i = \left\{ \begin{array}{ll} 1 + (s + 1) - s & \text{if $o_i = \text{push}$} \\ 1 + (s - 1) - s & \text{if $o_i = \text{pop}$} \\ k + (s - k) - s & \text{if $o_i = \text{multipop}$} \end{array} \right. = \left\{ \begin{array}{ll} 2 & \text{if $o_i = \text{push}$} \\ 0 & \text{if $o_i = \text{pop}$} \\ 0 & \text{if $o_i = \text{multipop}$} \end{array} \right. $$

Which is the same as the accounting method. I can see a sort of relationship between the accounting and potential method, which in my mind is similar to the relationship between function and integral function, or function and derivative function. With this I mean, the in the accounting method we define a function $\hat{c}_i$ and we later compute a summation that bounds the actual worst case hopefully tighter than doing standard complexity analysis. In the potential method we instead define a function $\Phi$ that would allow to retrieve $\hat{c}_i$ using the finite difference, plus the actual cost. Is this correct? Is there also anything more subtle I'm still missing maybe? (some kind of clever observation regarding the two methods).

Also in both cases I still want to compute the actual cost per operation in order to perform the analysis. In the accounting method I need the summation to prove that the summation of the amortized costs bound the actual cost, in the potential method I need this cost per single operation. Computing the actual cost would be something I'd do normally in complexity analysis. Therefore the question is where is the actual advantage in using these two methods?

$\endgroup$
  • $\begingroup$ They are simply to ways of looking at the same thing. $\endgroup$ – Raphael Mar 7 '18 at 19:52
  • $\begingroup$ @Raphael, yes of course. But the point is probably that using one method instead of the other one makes things easier I guess. $\endgroup$ – user8469759 Mar 8 '18 at 10:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.