Suppose we have a potential function such that (D i ) (D 0 ) for all i, but (D 0 ) 0 Show that there exists a potential function such that (D 0 ) 0, (Di ) 0 for all i 1, and the amortized costs using are the same as the amortized costs using ...

Solution Let di ci We can then define a new potential function D0 di ci 1 and a new po ...

Suppose we have a potential function such that (D i ) (D 0 ) for all

Question:

Suppose we have a potential function Φ such that Φ(D_i)≥ Φ(D₀) for all i, but Φ(D₀) ≠ 0. Show that there exists a potential function Φ′ such that Φ′(D₀) = 0, Φ′(Di ) ≥ 0 for all i ≥ 1, and the amortized costs using Φ′ are the same as the amortized costs using Φ.

Fantastic news! We've Found the answer you've been seeking!