Probabilistic Recurrence Relations for
Work and Span of Parallel Algorithms

arXiv:1704.02061v1 [] 7 Apr 2017

Joseph Tassarotti
Computer Science Department, Carnegie Mellon University
jtassaro@cs.cmu.edu

Abstract
In this paper we present a method for obtaining tail-bounds for random variables satisfying certain
probabilistic recurrences that arise in the analysis of randomized parallel divide and conquer algorithms.
In such algorithms, some computation is initially done to process an input x, which is then randomly split
into subproblems h1 (x), . . . , hn (x), and the algorithm proceeds recursively in parallel on each subproblem.
The
Pn total work on input x, W (x), then satisfies a probabilistic recurrence of the form W (x) = a(x) +
i=1 W (hi (x)), and the span (the longest chain of sequential dependencies), satisfies S(x) = b(x) +
maxn
i=1 S(hi (x)), where a(x) and b(x) are the work and span to split x and combine the results of the
recursive calls.
Karp has previously presented methods for obtaining tail-bounds in the case when n = 1, and under
certain stronger assumptions for the work-recurrence when n ≥ 2, but left open the question of the
span-recurrence. We first show how to extend his technique to handle the span-recurrence. We then
show that in some cases, the work-recurrence can be bounded under simpler assumptions than Karp’s by
transforming it into a related span-recurrence and applying our first result. We demonstrate our results
by deriving tail bounds for the work and span of quicksort and the height of a randomly generated binary
search tree.

1

1

Introduction

The analysis of sequential divide-and-conquer algorithms involves analyzing recurrences of the form
W (x) = a(x) +

n
X

W (hi (x))

(1)

i=1

where a(x) is the “toll” cost to initially process an input of size x and split it into smaller inputs h1 (x), . . . , hn (x),
which are then processed recursively. When the functions h1 , . . . , hn are deterministic, there are a number
of well-known “cook-book” methods that can be used to obtain asymptotic bounds in many cases [1, 6, 14].
In algorithms where the recursive calls are done in parallel, another measure of cost becomes important:
the span [3, 4] measures the longest sequential dependency in the execution, and is important for measuring
the speed-up of the algorithm as the number of processors is increased. The recurrence for the span has the
form:
n
S(x) = b(x) + max S(hi (x))
(2)
i=1

where b(x) is the span for processing and dividing the input, but we take the maximum of the recursive calls
instead of summing because we are interested in the longest dependency. These kinds of recurrences involving
maxima also arise when analyzing heights of search trees or stack space usage of sequential algorithms.
Again, when the hi are deterministic, the above recurrence often simplifies to something of the form S(x) =
b(x) + S(hi (x)) for some hi , and so the usual cook-book methods can be used to obtain asymptotic bounds.
However, when the hi (x) are random variables (either because the algorithm uses randomness when
dividing the input into subproblems, or when considering average case complexity), then W (x) and S(x) are
themselves random variables and the situation is more complicated. First, when considering the expected
value of the work, we can at least use linearity of expectation to get
E [W (x)] = a(x) +

n
X

E [W (hi (x))]

(3)

i=1

and a variety of techniques can be used to solve the resulting recurrence. But in the case of span, expectation
does not commute with taking a maximum, so that in general E [maxni=1 S(hi (x))] 6= maxni=1 E [S(hi (x))],
and we merely have E [maxni=1 S(hi (x))] ≥ maxni=1 E [S(hi (x))]. As a result, the expected value of the span
does not obey a simple recurrence. A second source of complexity is that we may be interested not just in
obtaining bounds on expectation, but may also wish to know that with high probability the work and span
are close to this expected value.
Although a number of methods are known for obtaining results for certain recurrences of these forms [7,
8, 9, 11], these often rely on sophisticated tools from probability theory or analytic combinatorics and are
not simple cook-book results that can be easily applied.
In contrast to some of the more advanced techniques mentioned above, Karp [12] has presented relatively
simple methods for obtaining tail-bounds for work recurrences of the form in Equation 1:
Theorem 1 ([12, Theorem 1.2]). Suppose n = 1 in Equation 1, so that W (x) = a(x) + W (h(x)) where h(x)
is a random variable such that 0 ≤ h(x) ≤ x. Furthermore, assume E [h(x)] ≤ m(x) where 0 ≤ m(x) ≤ x
and m(x)/x is non-decreasing. Suppose u is a solution to the recurrence u(x) = a(x) + u(m(x)). If a and u
are continuous and a is strictly increasing on the set {x | a(x) > 0}, then for all positive integers w,
w

m(x)
P rob [W (x) > u(x) + wa(x)] ≤
x
In other words, if there is a single recursive call and we can suitably bound the expected size of h(x),
this lets us derive tail-bounds for the work in terms of a simple deterministic recurrence. Often m(x)/x will
be a constant fraction such as 1/2 or 3/4, so that the recurrence for u can be solved straightforwardly. A
second result covers the case where there is more than one recursive call:
Theorem 2 ([12, Theorem 1.5]). Let W obey the recurrence in Equation
Pn1. Suppose that for all (y1 , . . . , yn )
in the support of the joint distribution (h1 (x), . . . , hn (x)), E [W (x)] ≥ i=1 E [W (yi )]. Then for all positive
w:
1
P rob [W (x) ≥ (w + 1)E [W (x)]] < w
e
2

Both of these results are proved in the more general setting where the distributions of the hi (and hence
W ) may depend on more than just the size of the input, that is we consider recurrences:
W (z) = a(size(z)) +

n
X

W (hi (z))

(4)

i=1

where size(z) gives the size of input z.
Pn
Despite the generality of the above results, Karp notes that the assumption E [W (x)] ≥ i=1 E [W (yi )]
in Theorem 2 is not satisfied in some important cases. Even when it is satisfied, it may be difficult to show
since we need to know more than just the asymptotic value of E [W (x)]. Moreover, Karp mentions the
problem of handling the span-recurrences of the form in Equation 2 but leaves it open. Although subsequent
work [5] has presented an alternative to Theorem 1 that has some weaker assumptions, to our knowledge, no
follow-up has satisfactorily extended these results to span-recurrences or weakened the assumption needed
for Theorem 2.
In this paper we present a generalization of Theorem 1 to handle both span and work-recurrences for the
general case of n ≥ 1, without the restrictive assumption needed in Theorem 2. There are two key aspects
of our results that distinguish them:
• Rather than having a function m such that E [h(x)] ≤ m(x), we require E [maxni=1 hi (x)] ≤ m(x).
That is, m(x) must bound the expectation of the maximum of the problem sizes. In many applications,
bounding this is not significantly more difficult than the bound needed in Theorem 1.
• Instead of checking
that for all (y1 , . . . , yn ) in the support of the distribution (h1 (x), . . . , hn (x)),
Pn
E [W (x)] ≥
E
[W
(yi )], our theoremsPare parameterized by functions g1 and g2 for which we
i=1
P
require g1 (x) ≥ ni=1 g1 (yi ) and g2 (x) ≥ ni=1 g2 (yi )). Often, it is easier to exhibit g1 and g2 with
these properties than to check that the expected value has them.
Simplified forms of our main results are:
Theorem 3. Suppose S(x) = b(x) + maxni=1 S(hi (x)), where for all x, there exists some k such that the
recurrence terminates after at most k recursive calls. Let g1 bePa monotone function such that for all
(y1 , . . . , yn ) in the support of the distribution (h1 (x), . . . , hn (x)),
g1 (yi ) ≤ g1 (x). Furthermore, assume
E [maxni=1 hi (x)] ≤ m(x) where 0 ≤ m(x) ≤ x and m(x)/x is non-decreasing. Assume u is a solution to
the recurrence u(x) = b(x) + u(m(x)). If b and u are continuous and b is strictly increasing on the set
{x | b(x) > 0}, then for all positive integers w and x such that g1 (x) ≥ 1,
w

m(x)
P rob [S(x) > u(x) + wb(x)] ≤ g1 (x)
x
Pn
Theorem 4. Suppose W (x) = a(x) + i=1 W (hi (x)), and the same assumptions about termination of the
recurrence and m(x) hold as in Theorem 3. Let
Pg1 and g2 be functions
P such that for all (y1 , . . . , yn ) in the
support of the distribution (h1 (x), . . . , hn (x)),
g1 (yi ) ≤ g1 (x) and
g2 (yi ) ≤ g2 (x). Now, let u(x) be a
solution to the recurrence u(x) = a(x)/g2 (x) + u(m(x)). If a/g2 and u are continuous and a/g2 is strictly
increasing on the set {x | a(x)/g2 (x) > 0}, then for all positive integers w and g1 (x) ≥ 1:
w

m(x)
P rob [W (x) > g2 (x)u(x) + wa(x)] ≤ g1 (x)
x
Notice that the tail bound has an additional factor of g1 (x) compared with Theorem 1. Generally we will
use g1 (x) = x, and we will be interested in w such that the term (m(x)/x)w is already exponentially small
compared to g1 (x), so we will still be able to show that the desired bound holds with high probability. Note
that Theorem 1 is indeed a special case of these results, since in the degenerate case where n = 1, we may
take g1 (x) = g2 (x) = 1, and we obtain Theorem 1. Moreover, we prove a more general form that handles
the case when the distribution of the hi may depend on more than just the problem size.
Our proofs are based on the proof of Theorem 1, so we begin by outlining Karp’s proof of Theorem 1 in a
more general setting than the version quoted above (§2). We focus only on those parts that will subsequently
3

change in our extensions. Next, we show how to extend the proof to handle span recurrences (§3) to obtain
Theorem 3. Then, we show that in certain cases, bounding a work recurrence can be reduced to bounding
span recurrences (§4), so that we can deduce Theorem 4 from Theorem 3. We then apply our method to
some examples (§5). Finally, we discuss related work (§6).

2

Karp’s method

In this section we give Karp’s proof of a more general version of Theorem 1, where W and h are functions of
problem instances rather than just their sizes. Let I be the domain of problem inputs, and let size : I → R+
give the size of a problem. Then, we are interested in a recurrence of the form:
W (z) = a(size(z)) + W (h(z))

(5)

where h(z) is a random variable such that 0 ≤ size(h(z)) ≤ size(z). Let us first clarify what we mean by
such a probabilistic recurrence. We do not mean that W (z), as a function from the sample space Ω to R, is
equal to the expression on the right; rather, this is a statement about equality of distributions. That is, for
all z and r ∈ R:
X
P rob [W (z) > r] =
P rob [h(z) = y] · P rob [W (y) > r − a(size(z))]
(6)
y

Since we are interested in bounding P rob [W (z) > r], the recurrence only needs to be an inequality:
X
P rob [W (z) > r] ≤
P rob [h(z) = y] · P rob [W (y) > r − a(size(z))]

(7)

y

The proof relies on the following lemma:
Lemma 1 ([12, Lemma 3.1]). Let X be a random variable with values in the range [0, x]. Suppose f : R → R
is a non-negative function such that f (0) = 0, and there exists some constant c such that for all y ≥ c,
f (y) = 1 and f (y)/y is non-decreasing on the interval (0, c]. Then:
E [f (X)] ≤

E [X] f (min(x, c))
min(x, c)

Proof. We start by showing that for all y such that 0 ≤ y ≤ x,
yf (min(x, c))
min(x, c)
If y = 0 the result is immediate since f (0) = 0. Otherwise, if x ≤ c, then we have f (y)/y ≤ f (x)/x, and the
result follows. For the case where x > c, we have two sub-cases:
f (y) ≤

• If y ≤ c, then we again have f (y)/y ≤ f (c)/c and so we are done.
y
• If y > c, then f (y) = 1 = f (c) ≤ f (c) .
c
Letting F be the CDF of X, we have:
Z x
Z x
yf (min(x, c))
E [X] f (min(x, c))
f (y) dF (y) ≤
E [f (X)] =
dF (y) =
min(x,
c)
min(x, c)
0
0
Theorem 5 ([12, Theorem 3.3]). Let W satisfy the recurrence in Equation 7 for z such that size(z) > d.
That is, there is some point d at which the recurrence ends. Assume a(x) = 0 for x ∈ [0, d] and a(x) is
monotone and continuous on (d, ∞). Suppose E [h(x)] ≤ m(x) where 0 ≤ m(x) ≤ x and m(x)/x is nondecreasing. Assume u : R → R is a monotone solution to the recurrence u(x) ≥ a(x) + u(m(x)) which is
continuous on (d, ∞). Let u′ : R → R+ be an inverse of u above d, that is: u′ (u(x)) = x for x > d, and
similarly u(u′ (y)) = y for y > u(d). Assume for all x ≤ d, u(x) = u(d), and u(x) bounds the support of
W (x) for x ≤ d.
Then for all z and r, P rob [W (z) > r] ≤ Dr (size(z)), where:
4

1. If r ≤ u(d) then Dr (x) = 1
2. If r > u(d):
(a) If x ≤ d then Dr (x) = 0
(b) If x > d and u(x) ≥ r then Dr (x) = 1
(c) If x > d and u(x) < r then
Dr (x) =



 r−u(x)
m(x) ⌈ a(x) ⌉
x
m
l
x
)
u′ (r − a(x) r−u(x)
a(x)

When r = u(x) + wa(x) for integer w, Dr (x) simplifies to the bound stated in Theorem 1 in the introduction.
Note: The statement here is slightly different than Theorem 3.3 in [12]. In particular, there u is a
minimal, invertible solution to the deterministic recurrence and the result uses the inverse u−1 rather than
some u′ . Furthermore, a is assumed to be strictly increasing on (d, ∞) and continuous everywhere, and m
is also continuous (so as to imply continuity and invertibility of u). This continuity and strictly increasing
assumption rules out the case where a(x) = 1 for x > d and a(x) = 0 for x ≤ d, which arises in some examples,
so Karp has a separate result for this case. However, the proof does not actually rely on continuity of a
everywhere or that it be strictly increasing instead of merely monotone, so we prefer the formulation above
which avoids the need for an additional separate theorem.


Proof. We will only give the proof in the case where for all z, there exists some k such that P rob size(hk (z)) > d =
0. See [15] for discussion of the proof in a more general setting.
For concision, let us define Kr (z) = P rob [W (z) > r]. The strategy of the proof is to inductively define
a sequence of functions Kri for i ∈ N, then show that Kr (z) is bounded by supi Kri (z), and finally prove by
i
induction on i that D bounds each of the K
 .

First, Equation 7 implies Kr (z) ≤ E Kr−a(size(z)) (h(z)) when size(z) > d. We will use a similar
“recurrence” to define K i by:
(
1 if r < u(d)
0
Kr (z) =
0 otherwise
h
i
i
(h(z))
Kri+1 (z) = E Kr−a(size(z))

For all i, Kri (z) ≤ Kri+1 (z) and Kri (z) ≤ 1 so supi Kri (z) exists. First we note that if size(z) ≤ d, then
Kr (z) ≤ Kri (z).


Next, we claim that if Kri (z) < Kr (z) then P rob size(hi (z)) > d > 0. The proof is by induction on i. If
i = 0, then we must show P rob [size(z) > d] > 0, but this is immediate since if not we know Kr (z) ≤ Kr0 (z),
contradicting
our assumption
of the opposite inequality. For the inductive case, Kri+1 (z) < Kr (z) implies
h
i


i
E Kr−a(size(z)) (h(z)) < E Kr−a(size(z)) (h(z)) . Hence for some y such that P rob [h(z) = y] > 0, we must


i
have Kr−a(size(z))
(y) < Kr−a(size(z)) (y). By the induction hypothesis, we have that P rob size(hi (y)) > d >




0, hence P rob size(hi+1 (z)) > d ≥ P rob [h(z) = y] · P rob size(hi (y)) > d > 0.
This implies that Kr (z) ≤ supi Kri (z), for if not, then for all i we would have Kri (z) < Kr (z), which
would imply that for all i there would be some non-zero probability that the recursion would continue for
at least i calls, contradicting our hypothesis about W .
We then show by induction on i that Kri (z) ≤ Dr (size(z)). A key part of the induction involves applying
Lemma 1 to the function Dr for some particular r. To do so, one must show that Dr (x)/x is non-decreasing
on the interval (0, u′ (r)]. We will not reproduce Karp’s proof of this fact, since our later proofs will re-use this
same Dr function. Nevertheless, the idea is to first divide up (0, u′ (r)] into subintervals on which ⌈ r−u(x)
a(x) ⌉
is constant and show that Dr (x)/x is non-decreasing on these intervals. Then, one shows that Dr (x)/x
is continuous at the ends of these subintervals, which proves monotonicity on (0, u′ (r)]. This is where the
continuity assumptions on a and u are used.
5

From there, the base case of the induction showing Kri (z) ≤ Dr (size(z)) is straight-forward. For the
inductive case, we have
h
i
i
Kri+1 (z) = E Kr−a(size(z))
(h(z))


≤ E Dr−a(size(z)) (h(z))
Dr−a(size(z)) (min(size(z), u′(r − a(size(z)))))
min(size(z), u′(r − a(size(z))))
(by Lemma 1 with X = size(h(z)), f = Dr−a(size(z)) , and c = u′ (r − a(size(z))))
≤ E [size(h(z))]

Dr−a(size(z)) (min(size(z), u′ (r − a(size(z)))))
min(size(z), u′ (r − a(size(z))))
= Dr (size(z))
≤ m(size(z))

3

Span Recurrences

We now extend the result from the previous section to handle probabilistic span recurrences of the form:
n

S(z) ≤ a(size(z)) + max S(hi (z))
i=1

where 0 ≤ size(hi (z)) ≤ size(z). In terms of the CDF of S(z) this is:
P rob [S(z) > r] ≤

X

y1 ,...,yn

h n
i
P rob [(h1 (z), . . . , hn (z)) = (y1 , . . . , yn )] · P rob max S(yi ) > r − a(size(z)) (8)
i=1

Recall from the introduction that the key idea of our result is that we now require a bound on the expected
maximum of the
Pn sizes of the subproblems h1 (z), . . . , hn (z), and we introduce a parameter g1 such that
g1 (size(x)) ≥ i=1 g1 (size(yi )) for all (y1 , . . . , yn ) in the support of the joint distribution (h1 (z), . . . , hn (z)).
We start by proving a generalization of Lemma 1 which suggests the role that these assumptions will play:
+
+
Lemma 2. Let X : Ω → [0, x]n be a random vector where
P n ∈ N . Let g : R → R be a function such that
for all (y1 , . . . , yn ) in the support of X, 0 ≤ g(yi ) and i g(yi ) ≤ g(x). Suppose f : R → R is a non-negative
function such that f (0) = 0, and there exists some constant c such that for all y ≥ c, f (y) = 1 and f (y)/y
is non-decreasing on the interval (0, c]. Then:
" n
#
X
E [maxni=1 Xi ] f (min(x, c))
E
g(Xi )f (Xi ) ≤ g(x)
min(x, c)
i=1

where Xi is the ith component of the random vector X.
Proof. It suffices to show that for all (y1 , . . . , yn ) in the support of X,
n
X

g(yi )f (yi ) ≤ g(x)

i=1

(maxni=1 yi )f (min(x, c))
min(x, c)

We have:
n
X
i=1

! 

 X

n
n
n
g(yi )f (yi ) ≤ max f (yj )
g(yi ) ≤ max f (yj ) g(x)
j=1

i=1

j=1

Monotonicity of f (x)/x implies f is monotone. Furthermore, by the argument in Lemma 1, we know that
y f (min(x,c))
for each j, f (yj ) ≤ j min(x,c) . Hence, we have:

6

n
X
i=1



n
g(yi )f (yi ) ≤ max f (yj ) g(x)
j=1
n

≤ f (max yj )g(x)
j=1

maxnj=1 yj f (min(x, c))
≤
g(x)
min(x, c)

The proof of the next result has the same overall structure as that of Theorem 5, except we use the above
lemma in place of Lemma 1.
Theorem 6. Let S satisfy the recurrence in Equation 8 for z such that size(z) > d. Assume for all z
there exists k such that for all i1 , . . . , ik we have P rob [size(hi1 (. . . (hik (z)))) > d] = 0. Assume a(x) = 0
for x ∈ [0, d] and a(x) is monotone and continuous on (d, ∞). Suppose E [maxni=1 hi (x)] ≤ m(x) where
0 ≤ m(x) ≤ x and m(x)/x is non-decreasing. Let u, u′ be as in Theorem 5, under analogous assumptions.
Furthermore, let g1 : R → R+ be a monotone function such that for all x > d, g1 (x) ≥ 1. Assume for all z
such that size(z) > d, and all (y1 , . . . , yn ) in the joint distribution of (h1 (z), . . . , hn (z)):
n
X

g1 (size(yi )) ≤ g1 (size(z))

i=1

Then for all z and r such that g1 (size(z)) ≥ 1, we have P rob [S(z) > r] ≤ g1 (size(z)) · Dr (size(z)) where
Dr (size(z)) is as in Theorem 5.
Proof. Set Kr (z) = P rob [S(z) > r]. By the union bound, Equation 8 implies
Kr (z) ≤

n
X
i=1



E Kr−a(size(z)) (hi (z))

As before, we will inductively define a family of functions K i using this same recurrence, show that their
suprema bounds K, and then inductively bound the K i . Define Kri (z) by:
(
1 if r < u(d)
0
Kr (z) =
0 otherwise
n
h
i
X
i
E Kr−a(size(z))
(hj (z)) )
Kri+1 (z) = min(1,
j=1

For all i, Kri (z) ≤ Kri+1 (z) and Kri (z) ≤ 1, so supi Kri (z) exists. As before, if size(z) ≤ d, then Kr (z) ≤
Kri (z). Here, if Krn (z) < Kr (z) then P rob [size(hi1 (. . . (hin (z)))) > d] > 0 for some sequence i1 , . . . , in . The
proof is by induction on n, where the base case is immediate.
For the inductive
if Krn+1 (z) < Kr (z)
h
i Pcase,


P
n
n+1
n+1
we must have that Kr (z) < 1, so Kr (z) = j E Kr−a(size(z)) (hj (z)) < j E Kr−a(size(z)) (hj (z)) .

n
Hence for some i and y such that P rob [hi (z) = y] > 0, we must have Kr−a(size(z))
(y) < Kr−a(size(z)) (y).
By the induction hypothesis, P rob [size(hi1 (. . . hin (y))) > d] > 0. Then the sequence i1 , . . . , in , i suffices. It
follows that Kr (z) ≤ supi Kri (z), or else our assumption about the termination of the recurrence would be
violated.
When r < u(d) and size(z) ≥ d, we have Kri (z) ≤ 1 ≤ g1 (size(z)) · Dr (size(z)). For the case when
r ≥ u(d) we prove by induction on i that Kri (z) ≤ g1 (size(z)) · Dr (size(z)). The base case is similar to that

7

of Theorem 5. For the inductive step, the only non-trivial sub-case is when size(z) > d and r > u(size(z)).
Then we have:
Kri+1 (z) ≤

n
X
j=1

≤

n
X
j=1

i
h
i
(hj (z))
E Kr−a(size(z))


E g1 (size(hj (z))) · Dr−a(size(z)) (hj (z))



Dr−a(size(z)) (min(size(z), u′(r − a(size(z)))))
n
≤ g1 (size(z)) · E max(size(hj (z)))
j=1
min(size(z), u′ (r − a(size(z))))

(by Lemma 2 with X = (size(h1 (z)), . . . , size(hn (z))), f = Dr−a(size(z)) ,
g = g1 , and c = u′ (r − a(size(z))))
Dr−a(size(z)) (min(size(z), u′(r − a(size(z)))))
min(size(z), u′(r − a(size(z))))
= g1 (size(z)) · Dr (size(z))

≤ g1 (size(z)) · m(size(z))

In the second line, when we apply the induction hypothesis, we must check that r − a(size(z)) ≥ u(d). This
follows from the fact that r > u(size(z)) ≥ a(size(z)) + u(m(size(z))) ≥ a(size(z)) + u(d).

4

Work Recurrences

Finally we show in this section that in some cases, work-recurrences can be transformed into analogous
span-like recurrences. Our starting point is a recurrence:
W (z) ≤ a(size(z)) +

n
X

W (hi (z))

(9)

i=1

which terminates when size(z) ≤ d. Let g2 : R → R+ bePa function such that for all (y1 , . . . , yn ) in the
support of the distribution (size(h1 (z)), . . . , size(hn (z))),
g2 (yi ) ≤ g2 (x). Consider the random variable
H(z) = W (z)/g2 (size(z)). We have:
n

H(z) ≤

X
a(size(z))
+
g2 (size(z)) i=1
n

=

X
a(size(z))
+
g2 (size(z)) i=1
n




1
W (hi (z))
g2 (size(z))




g2 (size(hi (z)))
H(hi (z))
g2 (size(z))




g2 (size(hi (z))) n
max H(hj (z))
g2 (size(z)) j=1

n 
X
g2 (size(hi (z)))
a(size(z))
n
max H(hj (z))
+
=
j=1
g2 (size(z)) i=1
g2 (size(z))

X
a(size(z))
≤
+
g2 (size(z)) i=1

≤

a(size(z))
n
+ max H(hj (z))
j=1
g2 (size(z))

That is, we see H obeys a span-like recurrence with toll-function a/g2 . Since P rob [H(z) > r] =
P rob [W (z) > rg2 (size(z))], we can apply the theorem from the previous section to H and thereby derive a
tail-bound for W , giving us:
Theorem 7. Let W satisfy the recurrence in Equation 9 for z such that size(z) > d. Assume for all z there
exists k such that for all i1 , . . . , ik we have P rob [size(hi1 (. . . (hik (z)))) > d] = 0. Suppose E [maxni=1 hi (x)] ≤
8

m(x) where 0 ≤ m(x) ≤ x and m(x)/x is non-decreasing. Let u be a solution to the recurrence u(x) ≤
a(x)/g2 (x) + u(m(x)) under analogous assumptions as the previous theorems. Furthermore, let g1 , g2 : R →
R+ be monotone functions where for all x > d, g1 (x) ≥ 1. Assume for all z such that size(z) > d, and all
(y1 , . . . , yn ) in the joint distribution of (h1 (z), . . . , hn (z)):
n
X

g1 (size(yi )) ≤ g1 (size(z))

and

n
X

g2 (size(yi )) ≤ g2 (size(z))

i=1

i=1

Finally, let a(x)/g(x) = 0 for x ∈ [0, d] and assume a(x)/g(x) is monotone and continuous on (d, ∞). Then
for all z and r such that g1 (size(z)) ≥ 1, we have P rob [W (z) > r] ≤ g1 (size(z)) · Dr/g2 (size(x)) (size(z))
where Dr (size(z)) is as in Theorem 5, using the toll function a/g2 .

5

Examples

We now apply the previous results to examples.
Quicksort Let l be a list and write |l| for the length of the list. The work and span owing to the comparisons
involved in parallel randomized quicksort satisfy the following recurrences:
W (l) = (|l| − 1) + W (h1 (l)) + W (h2 (l))
S(l) = log |l| + max(S(h1 (l)), S(h2 (l)))
where E [max(|h1 (l)|, |h2 (l)|)] ≤ 7|l|
8 when |l| > 1 and is 0 otherwise; moreover, |h1 (l)| + |h2 (l)| ≤ |l| − 1.
Note that this is a case where the distributions of the sizes of the sublists h1 (l) and h2 (l) depend on more
than just the size of l: in particular, if l contains multiple versions of the same element, then the sublists will
tend to be smaller than if all elements of l are distinct. Therefore, the more general formulations of Theorem
2
6 and Theorem 7 are useful here. For span, we apply Theorem 6 with m(x) = 7x
8 , u(x) = (log8/7 x + 1) ,
and g1 (x) = x, to get that for all positive integers w,
 w
h
i
7
2
P rob S(l) > (log8/7 |l| + 1) + w log |l| ≤ |l|
8
when |l| ≥ 1. Take w to be ⌈ (logk8/7) log8/7 |l|⌉ for integer k so that we have
i  1  logk 8 −1
h
7
2
P rob S(l) > (k + 1)(log8/7 |l| + 1) ≤
|l|
For the work, we take g2 to be:


1

if x ≤ 1
2
g2 (x) = 1
if 1 < x < 2


x − 1 if x ≥ 2

In this case, in order to solve the recurrence for u, it is easier if we take m to be
(
0
if x < 8/7
m(x) = 7x
if x ≥ 8/7
8
Applying Theorem 7 with u(x) = log8/7 (x) + 1 we obtain:
 w
h
i
7
P rob W (l) > (|l| − 1)(log8/7 |l| + 1) + w(|l| − 1) ≤ |l|
8

9

Here taking w to be ⌈k log8/7 |l|⌉ for integer k we have
h

i  1 k−1
P rob W (l) > (k + 1) |l| log8/7 |l| + |l| ≤
|l|
Karp shows in [12] that the quicksort work recurrence does satisfy the hypotheses of Theorem 2, which
one can check knowing that E [W (|l|)] = 2((|l|+1)(H|l| −1)−(|l|−1)), where Hn is the nth Harmonic number.
However, it is much easier to check that g2 satisfies the analogous hypothesis of our result. Moreover, the
resulting bound obtained by Karp’s Theorem 2,
P rob [W (l) > (a + 1)E [W (l)]] ≤

1
ea

is weaker than the bound we obtain above.
Height of search trees Consider random binary search trees generated by successively inserting the
elements of a permutation of {1, . . . , n}, with all permutations equally likely. The height H(n) of such a tree
obeys the following probabilistic recurrence:
H(n) = 1 + max(H(h1 (n)), H(h2 (n)))
where again E [max(h1 (n), h2 (n))] ≤ 7n
8 and h1 (n) + h2 (n) = n − 1. Therefore we can apply Theorem 6 with
similar choice of m as in the previous examples, and with u(n) = log8/7 (n) + 1 to get:
 w
7
P rob H(n) > (log8/7 n + 1) + w ≤ n
8
h

i

Again, for appropriate choice of w this yields:
h
i  1 k−1
P rob H(n) > (k + 1)(log8/7 n + 1) ≤
n
A similar argument works for a large class of tree structures, such as radix trees and quad trees, so long as
we can bound the expected value of the maximum of the sizes of the subtrees.

6

Conclusion and Related Work

We have presented a way to extend Theorem 1 to span and work recurrences, answering the open questions
posed by Karp in [12]. Our result for work recurrences is easier to apply than Theorem 2 and gives stronger
bounds in cases like the analysis of quicksort.
Of course, just as with the original theorems, more precise bounds can be obtained by instead using
more advanced techniques. The books by Flajolet and Sedgewick [11] and Drmota [9] give an overview of
techniques from analytic combinatorics and probability theory that can be used to analyze processes that
give rise to these kinds of recurrences.
Nevertheless, Karp has argued convincingly that it is still useful to have easy to apply cook-book techniques for use in situations where less precise results are often obtained using ad-hoc methods. Cookbook methods are common and well known for analyzing deterministic divide-and-conquer recurrences (e.g.
[1, 14, 10]). However, for randomized divide-and-conquer, there are far fewer results. The method of Roura
[14] applies to the recurrence for the expected number of comparisons in quicksort. Bazzi and Mitter [2]
extend the Akra–Bazzi method [1] to derive asymptotic bounds for expected work recurrences.
Chaudhuri and Dubhashi [5] study the unary probabilistic recurrences of Theorem 1 and give an alternative result that does not require m(x)/x to be non-decreasing (but in this case, the bound is weaker
than Theorem 1). They suggest that one advantage of their proof is that it only uses common tools from
probability theory like Markov’s inequality and Chernoff bounds. It would be interesting to see if some of
the ideas we used here can also be used to extend their version to handle general span and work recurrences.

10

In a technical report, Karpinski and Zimmermann [13] also modify Theorem 1 to try to handle span and
work recurrences. However, the bounds they obtain appear to be weaker
to
w than ours. For instance, applied
the span recurrence of quicksort, their result gives a bound of 1 − n1
where our Theorem 6 gives n( 87 )w .
That is, the bounds they give do not appear to be sufficient to establish high probability bounds on run-time.
Moreover, their proof modifies the Dr (x) function and applies Lemma 1, but they do not give a proof for
why Dr (x)/x remains non-decreasing, and Karp’s strategy for showing that it is non-decreasing does not
appear to generalize to their version.
Acknowledgments The author thanks Robert Harper, Jean-Baptiste Tristan, Victor Luchangco, Guy
Blelloch, and Guy L. Steele Jr. for helpful discussions. This research was conducted with U.S. Government
support under and awarded by DoD, Air Force Office of Scientific Research, National Defense Science and
Engineering Graduate (NDSEG) Fellowship, 32 CFR 168a. Any opinions, findings and conclusions or recommendations expressed in this material are those of the author and do not necessarily reflect the views of
this funding agency.

References
[1] M. Akra and L. Bazzi. On the solution of linear recurrence equations. Comp. Opt. and Appl., 10(2):
195–210, 1998. doi: 10.1023/A:1018373005182. URL http://dx.doi.org/10.1023/A:1018373005182.
[2] L. Bazzi and S. K. Mitter.
The solution of
tions.
Algorithmica, 36(1):41–57, 2003.
doi:
http://dx.doi.org/10.1007/s00453-002-1003-4.

linear probabilistic recurrence rela10.1007/s00453-002-1003-4.
URL

[3] G. Blelloch and J. Greiner. Parallelism in sequential functional languages. In Proceedings of the 7th
International Conference on Functional Programming Languages and Computer Architecture, pages
226–237, 1995. ISBN 0-89791-719-7.
[4] R. D. Blumofe and C. E. Leiserson.
Scheduling
work stealing.
J. ACM, 46(5):720–748, 1999.
doi:
http://doi.acm.org/10.1145/324133.324234.

multithreaded computations by
10.1145/324133.324234.
URL

[5] S. Chaudhuri and D. P. Dubhashi.
Probabilistic recurrence relations revisited.
Theor. Comput. Sci., 181(1):45–56, 1997.
doi:
10.1016/S0304-3975(96)00261-7.
URL
http://dx.doi.org/10.1016/S0304-3975(96)00261-7.
[6] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and
to Algorithms (3. ed.).
MIT Press, 2009.
ISBN
http://mitpress.mit.edu/books/introduction-algorithms.

C. Stein.
Introduction
978-0-262-03384-8.
URL

[7] L. Devroye. A note on the height of binary search trees. J. ACM, 33(3):489–498, 1986. doi: 10.1145/
5925.5930. URL http://doi.acm.org/10.1145/5925.5930.
[8] M. Drmota. An analytic approach to the height of binary search trees. Algorithmica, 29(1):89–119,
2001. doi: 10.1007/BF02679615. URL http://dx.doi.org/10.1007/BF02679615.
[9] M. Drmota. Random Trees. Springer-Verlag Wien, 2009. ISBN 978-3-211-75355-2.
[10] M. Drmota and W. Szpankowski.
A master theorem for discrete divide and conquer
recurrences.
J. ACM, 60(3):16:1–16:49, 2013.
doi:
10.1145/2487241.2487242.
URL
http://doi.acm.org/10.1145/2487241.2487242.
[11] P.
Flajolet
and
R.
Sedgewick.
Analytic
Combinatorics.
bridge
University
Press,
2009.
ISBN
978-0-521-89806-5.
http://www.cambridge.org/uk/catalogue/catalogue.asp?isbn=9780521898065.

CamURL

[12] R. M. Karp. Probabilistic recurrence relations. J. ACM, 41(6):1136–1150, 1994. doi: 10.1145/195613.
195632. URL http://doi.acm.org/10.1145/195613.195632.
11

[13] M. Karpinski and W. Zimmermann. Probabilistic recurrence relations for parallel divide-and-conquer
algorithms. Technical Report TR-91-067, International Computer Science Institute (ICSI), 1991. URL
https://www.icsi.berkeley.edu/ftp/global/pub/techreports/1991/tr-91-067.pdf.
[14] S. Roura. Improved master theorems for divide-and-conquer recurrences. J. ACM, 48(2):170–205, 2001.
doi: 10.1145/375827.375837. URL http://doi.acm.org/10.1145/375827.375837.
[15] N. Young. Answer to: Understanding proof of theorem 3.3 in Karp’s probabilistic recurrence relations.
Theoretical Computer Science Stack Exchange. URL http://cstheory.stackexchange.com/q/37144.
URL:http://cstheory.stackexchange.com/q/37144 (version: 2016-12-13).

12

