2
$\begingroup$

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?

Shay

Improve this question
$\endgroup$
8
  • 3
    $\begingroup$ 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). $\endgroup$
    – Tsuyoshi Ito
    Sep 11, 2011 at 20:56
  • $\begingroup$ 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)? $\endgroup$
    – Shay Ben Moshe
    Sep 11, 2011 at 20:59
  • $\begingroup$ indeed. In fact the original explanation in the table expansion article is essentially a potential method, but correctly explained. $\endgroup$
    – Suresh Venkat
    Sep 11, 2011 at 21:00
  • 4
    $\begingroup$ theory.cs.uiuc.edu/~jeffe/teaching/algorithms/notes/… $\endgroup$
    – jbapple
    Sep 11, 2011 at 21:57
  • $\begingroup$ @jbapple make this an answer so it can be accepted, preventing Community from bumping it up again and again ? $\endgroup$
    – Suresh Venkat
    Sep 12, 2011 at 17:04

1 Answer 1

Reset to default
5
$\begingroup$

http://theory.cs.uiuc.edu/~jeffe/teaching/algorithms/notes/15-amortize.pdf specifically for amortization, and http://theory.cs.uiuc.edu/~jeffe/teaching/algorithms/ generally

Improve this answer
$\endgroup$

Your Answer

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

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