| Potential
method analysis |
|
|
|
|
|
|
|
|
|
|
|
| • | P(i)
is always positive. |
|||||||||
| – | Yes. We rehash when F ³ 1/2S, at
which point, |
|||||||||
| 4F=S. Etc… |
||||||||||
| • | Amortized
cost is constant |
|||||||||
| – | CA(i+1)=C(i+1)+P(i+1)-P(i) |
|||||||||
| = 3,
in both cases (previous slide) |
||||||||||