
Universität Bonn > Institut für Informatik > Abteilung V  
CSReports 1991  Copyright 1991 Universität Bonn, Institut für Informatik, Abt. V  
8572

Probabilistic Recurrence Relations for Parallel DivideandConquer Algorithms
Marek Karpinski, Wolf Zimmermann [Download PostScript] [Download PDF] We study two probabilistic recurrence relations that arise frequently in the analysis of parallel and sequential divideandconquer algorithms (cf.~\cite{Karp91}). 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),\ldots,h_k(x)$ and these subproblems are solved recursively. We assume that $\mbox{\it size}(h_i(z))$ are random variables. This occurs if either the {\em 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 estimate upper bounds on the probability distribution of $T(x)$ for %this two kinds of recurrence answering the open questions of Karp %\cite{Karp91}. We give a method for estimating ({\em tight}) {\em upper bounds} on the probability distribution of $T(x)$ for these two kinds of recurrence relations, answering the open questions of Karp in \cite{Karp91}. 

Last Change:
11/05/14 at 09:40:23
English 
Universität Bonn > Institut für Informatik > Abteilung V 