Probabilistic recurrence relations
Richard M. Karp · Journal of the ACM · 1994
This paper is concerned with recurrence relations that arise frequently m the analysis of divide-and-conquer algorithms.In order to solve a problcm instance of size x, such an algorlthm invests an amount of work a(x) to break the problem mto subproblems of sizes h l(x), hz(x), . . . .lr~(,r), and then proceeds to solve the subproblems.Our particular interest is in the case where the sizes hr(.r) are random variables; th]s may occur either because of randomization within the algorlthm or because the instances to be solved are assumed to be drawn from a probability distribution.When the h are random variables the running time of the algorithm on instances of size x is also a random variable T(x).We give several easy-to-apply methods for obtaining fairly tight bounds on the upper tails of the probability distribution of T(x), and present a number of typical applications of these bounds to the analysis of algorithms.The proofs of tbe bounds are based on an interesting analysis of optimal strategies in certain gambling games.