O'Reilly logo

Concentration of Measure for the Analysis of Randomized Algorithms by Alessandro Panconesi, Devdatt P. Dubhashi

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

4

Interlude: Probabilistic Recurrences

Karp [49] developed an attractive framework for the analysis of randomized algorithms. Suppose we have a randomized algorithm that, on input x, performs “work” a(x) and then produces a subproblem of size H(x), which is then solved by recursion. One can analyse the performance of the algorithm by writing down a “recurrence”:

image

(4.1)

Superficially this looks just the same as the usual analysis of algorithms via recurrence relations. However, the crucial difference is that in contrast with deterministic algorithms, the size of the subproblem produced here, H(x) is a random variable, and so (4.1) is a ...

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