Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I read about Potential Method when I was trying to understand some calculations.

I just can't understand how do you perform the calculation it self. How can you even define $O(n)-O(n)$ as it is used in the Wikipedia page? I just don't understand where is the calculation done.

Is there any good and simple example of this kind of analysis?


share|cite|improve this question
The Wikipedia article uses variable-length arrays with size doubling as an example. This is a good example, but the explanation in the Wikipedia article is next to incorrect. It is correct that the amortized cost of the insertion when the expansion occurs is O(1), but not because it is O(n)−O(n). – Tsuyoshi Ito Sep 11 '11 at 20:56
Yes I understand that, I actually proved that once in a much simpler way. Do you know any better explanation online (article, video, doesn't matter)? – Shay Ben Moshe Sep 11 '11 at 20:59
indeed. In fact the original explanation in the table expansion article is essentially a potential method, but correctly explained. – Suresh Venkat Sep 11 '11 at 21:00
Thanks @jbapple, this article answered all my question. – Shay Ben Moshe Sep 12 '11 at 9:40

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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