2
$\begingroup$

A sequence of $N$ operations is performed on a certain data structure.

The $i$-th operation costs $i$ if $i$ is a power of 2, else it costs 1.

How can I calculate the amortized cost for every operation using the potential function method?

$\endgroup$
  • 1
    $\begingroup$ What have you tried? Where did you get stuck? We want to help you with your specific problems, not just do your (home-)work. However, as it is we don't know what this problem is and thus how to help. See here for a relevant discussion. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? $\endgroup$ – D.W. May 19 '14 at 6:18
3
$\begingroup$

How about this. Assume we maintain a binary counter $C$ that counts the operations executed so far. Let $D_i$ be the data structure after the $i$-th operation. We then define as potential $\Phi(D_i)$ number of $\tt 1$-digits in $C$. As usual $c_i$ denotes the actual costs, and $\hat c_i$ the amortized costs.

If $i$ is not a power of two, then we have $$ \hat c_i = c_i + \Phi(D_i) - \Phi(D_{i-1}) \le 2 .$$ This is true since the addition of a $\tt 1$ on $C$ will turn one digit from $\tt 0$ to $\tt 1$ while possibly turning some digits from $\tt 1$ to $0$.

If $i$ is a power of two then clearly $$ \hat c_i = c_i + \Phi(D_i) - \Phi(D_{i-1})= i + 1 - (i-1) =2 .$$

As a final comment, the amortized costs do always depend on the potential function. So another potential function yields different amortized costs.

$\endgroup$
  • $\begingroup$ To avoid confusion, can we rewrite it as $\hat c_i = c_i + \Phi(D_i) - \Phi(D_{i-1})= 1 + i - (i-1) =2 $ $\endgroup$ – Mojo Jojo Sep 5 '16 at 12:46
1
$\begingroup$

I don't know about the potential function method, but to calculate the amortized cost, you compute the total cost of $n$ operations and divide by $n$. In this case, if we denote by $x_i$ the cost of the $i$th operation then $$ \sum_{i=1}^n x_i = n + \sum_{2^j \leq n} (2^j-1) \leq 3n, $$ and we can conclude that the amortized time $O(1)$. I'll let you carry out the calculation and detail, and figure out how to apply the potential function method.

$\endgroup$
  • $\begingroup$ Note: Your solution is the counting method for amortized analysis. The question asked explicitly for the potential function method. $\endgroup$ – NightRa May 18 '14 at 9:38
  • $\begingroup$ @NightRa I find it somewhat idiotic that a question asks for such a particular proof method. In "real life" you calculate the amortized complexity in whatever which way is the most appropriate. $\endgroup$ – Yuval Filmus May 18 '14 at 13:53
  • $\begingroup$ When learning about a topic it is a good way of practicing to work out how a complicated methods works on a simple problem. $\endgroup$ – Kaveh May 21 '14 at 0:30

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.