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?

  • 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, 2014 at 6:18

2 Answers 2


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.

  • $\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, 2016 at 12:46

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.

  • $\begingroup$ Note: Your solution is the counting method for amortized analysis. The question asked explicitly for the potential function method. $\endgroup$
    – NightRa
    May 18, 2014 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$ May 18, 2014 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, 2014 at 0:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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