<p><a href="http://theory.cs.uiuc.edu/~jeffe/teaching/algorithms/notes/15-amortize.pdf" rel="nofollow noreferrer">http://theory.cs.uiuc.edu/~jeffe/teaching/algorithms/notes/15-amortize.pdf</a> specifically for amortization, and <a href="http://theory.cs.uiuc.edu/~jeffe/teaching/algorithms/" rel="nofollow noreferrer">http://theory.cs.uiuc.edu/~jeffe/teaching/algorithms/</a> generally</p>

CC BY-SA 3.0
2011-09-12T18:11:09.047Z
2017-03-25T13:26:59.177Z
2017-03-25T13:26:59.177Z
jbapple
<p>I read about <a href="http://en.wikipedia.org/wiki/Potential_method" rel="nofollow">Potential Method</a> when I was trying to understand some calculations.</p>

<p>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.</p>

<p>Is there any good and simple example of this kind of analysis?</p>

<p>Shay</p>

CC BY-SA 3.0
2011-09-11T20:56:19.203Z
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
CC BY-SA 3.0
2011-09-11T20:59:04.547Z
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
CC BY-SA 3.0
2011-09-11T21:00:30.880Z
indeed. In fact the original explanation in the table expansion article is essentially a potential method, but correctly explained.
Suresh Venkat
CC BY-SA 3.0
2011-09-11T21:57:39.287Z
http://theory.cs.uiuc.edu/~jeffe/teaching/algorithms/notes/14-amortize.pdf
jbapple
CC BY-SA 3.0
2011-09-12T17:04:12.433Z
@jbapple make this an answer so it can be accepted, preventing Community from bumping it up again and again ?
Suresh Venkat
CC BY-SA 3.0
2011-09-12T18:08:00.580Z
@Suresh sure, no prob.
jbapple
CC BY-SA 3.0
2011-09-12T21:37:02.587Z
Note that $\cal{O}(n) - \cal{O}(n)$ is abuse of notation and should be handled with utmost care.
Raphael
CC BY-SA 3.0
2011-09-13T19:10:41.517Z
Thank you all, and yes, I do know that $O(n) - O(n)$ is actually $O(n)$.
Shay Ben-Moshe
<ds.algorithms><amortized-analysis>
Amortized Analysis - Potential Method
Shay Ben-Moshe
# Amortized Analysis - Potential Method

(Asked by: username_0 on 2011-09-11)

I read about [Potential Method](http://en.wikipedia.org/wiki/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

**Tags:** ds.algorithms, amortized-analysis

> **Comments:**
> **username_1**: 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).  
> **username_0**: 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)?  
> **username_2**: indeed. In fact the original explanation in the table expansion article is essentially a potential method, but correctly explained.  
> **username_3**: http://theory.cs.uiuc.edu/~jeffe/teaching/algorithms/notes/14-amortize.pdf  
> **username_2**: @username_3 make this an answer so it can be accepted, preventing Community from bumping it up again and again ?  
> **username_3**: @Suresh sure, no prob.  
> **username_4**: Note that $\cal{O}(n) - \cal{O}(n)$ is abuse of notation and should be handled with utmost care.  
> **username_0**: Thank you all, and yes, I do know that $O(n) - O(n)$ is actually $O(n)$.  

---

## 1 answers

### Answer by username_3 on 2011-09-12. Score: 5 | Accepted answer

<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


---

