| Tokens
as a potential function |
|
|
|
|
|
|
|
|
|
|
|
|
|
| • | potential
function at operation #i |
|||||||||||
| P(i)=
1 + 2F - S/2 |
||||||||||||
| – | F = #
of filled (non-empty) hash table slots |
|||||||||||
| – | S =
total # of hash table slots |
|||||||||||
| • | Actual
cost of operation of operation #i |
|||||||||||
| C(i) |
||||||||||||
| • | Amortized
cost of operation #(i+1): |
|||||||||||
| CA(i+1)=C(i+1)
+ ( P(i+1) – P(i) ) |
||||||||||||