O'Reilly logo

Algorithms Third Edition in C by Robert Sedgewick

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Property 22.13 The worst-case running time of the FIFO queue implementation of the preflow-push algorithm is proportional to V2E.Image

Proof: We bound the number of phases using a potential function. This argument is a simple example of a powerful technique in the analysis of algorithms and data structures that we examine in more detail in Part 8.

Define the quantity φ to be 0 if there are no active vertices and to be the maximum height of the active vertices otherwise, then consider the effect of each phase on the value of φ. Let h0 (s) be the initial height of the source. At the beginning, φ =h0 (s); at the end, φ = 0.

First, we note that the number ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required