Question: Suppose we have a potential function such that (D i ) (D 0 ) for all i, but (D 0 ) 0. Show
Suppose we have a potential function Φ such that Φ(Di)≥ Φ(D0) for all i, but Φ(D0) ≠ 0. Show that there exists a potential function Φ′ such that Φ′(D0) = 0, Φ′(Di ) ≥ 0 for all i ≥ 1, and the amortized costs using Φ′ are the same as the amortized costs using Φ.
Step by Step Solution
3.37 Rating (163 Votes )
There are 3 Steps involved in it
Solution Let di ci We can then define a new potential function D0 di ci 1 and a new po... View full answer
Get step-by-step solutions from verified subject matter experts
