Probabilistic Recurrence Relations for Parallel Divide-and-Conquer Algorithms

TitleProbabilistic Recurrence Relations for Parallel Divide-and-Conquer Algorithms
Publication TypeTechnical Report
Year of Publication1991
AuthorsKarpinski, M., & Zimmermann W.
Other Numbers697
KeywordsDevide-and-Conquer Algorithms, Parallel Algorithms, Probabilistic Recurrence Relations, Upper Bounds on Probability Distribution

We study two probabilistic recurrence relations that arise frequently in the analysis of parallel and sequential divide-and-conquer algorithms (cf. [Karp 91]). Suppose a problem of size x has to be solved. In order to solve it we divide it into subproblems of size h_1(x), ... ,h_k(x) and these subproblems are solved recursively. We assume that size(h_i(z)) are random variables. This occurs if either the break up step is randomized or the instances to be solved are drawn from a probability distribution. The running time T(z) of a parallel algorithm is therefore determined by the maximum of the running times T(h_i(z)) of the subproblems while the sequential algorithm is determined by the sum of the running times of the subproblems. We give a method for estimating tight upper bounds on the probability distribution of T(x) for these two kinds of recurrence relations, answering the open questions in [Karp 91].

Bibliographic Notes

ICSI Technical Report TR-91-067

Abbreviated Authors

M. Karpinski and W. Zimmermann

ICSI Publication Type

Technical Report