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}.