Rheinische Friedrich-Wilhelms-Universität Bonn Institut für Informatik
 
Abteilung V

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

Probabilistic Recurrence Relations for Parallel Divide-and-Conquer 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 divide-and-conquer 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

Powered by Zope