Since a subbutterfly does not begin to execute its algorithm until the
larger butterfly at the previous level of recursion is finished,
delay in excess of the time allotted to each butterfly accumulates
over the course of the algorithm. An *M*-input butterfly is allotted
time to perform its steps. However,
Steps 6, 7, and
8 are not guaranteed to terminate in time
. It is tempting to try to prove that these steps
terminate quickly with high probability. This approach fails because
at the lower levels of the recursion the problem size is so small that
nothing can be ascertained with high probability. Instead we must
argue that although delay may occur at any particular step, it is
unlikely that a lot of delay will accumulate over a sequence of steps.

The delay from Step 8 is relatively easy to analyze. This step requires time; the delay depends only on the congestion. Lemma 8.5 bounds the probability that the congestion is large.

There are two possible causes of delay in Steps 6 and 7. A poor set of random rows for the packets can cause congestion at some node, which guarantees that some packet will arrive at its destination late. On the other hand, even if the congestion is small, a poor choice for the random ranks used by the scheduling algorithm may delay a packet. The following pair of lemmas bounds the probability that the delay from these steps is large. The first is a restatement of the Theorem 2.9 in a slightly different form. It bounds the probability that a packet will be delayed when the congestion is small. The second puts this bound together with the bound that the congestion is large from Lemma 8.5.

**Proof:**
The proof of Theorem 2.9 shows that the
probability that any packet arrives at its destination after step
is at most

where and are constants. Suppose that . Then this probability is at most which is less than . Now let . Then the probability that any packet arrives at its destination after step (for some ) is at most , where .

to .667emto .667em

**Proof:**
For the sake of brevity, we examine
Step 7 only. A similar
analysis holds for Step 6.

We break the analysis into two cases according to whether the
congestion is small or large. Let *T* be the time at which the last
packet arrives. Then

We use Lemma 8.6
to bound the first term on the right. Plugging in
for *c* yields . We use
Lemma 8.5 to bound the second term on the right.
Plugging in for *c* yields . Since , and , , and are constants,
,
for sufficiently large *N*.

to .667emto .667em

The following lemma bounds the combined delay of Steps 6, 7, 8.

**Proof:**
Step 8 can be performed
deterministically in time . From Lemma 8.5 we
have , for *s > L*. For our
purposes, a weaker bound on this probability suffices. Since
is a constant, there is a constant such that
for sufficiently large *L*. Combining
this bound with that of Lemma 8.7 yields the desired
result.

to .667emto .667em

To complete our analysis of the algorithm, we need to bound the probability that more than delay accrues during the sort.

**Proof:**
The cumulative delay at the bottom level of the recursion is
the sum of the delay at each of the butterflies on the branch of the
recursion tree from the top level to the leaf. Let be the delay
beyond at the *i*th level of the recursion. Then by Lemma 8.8. Notice that
there is no dependence on *i* in this expression. Let *D* be the
cumulative delay on a branch of the recursion from the top level to a
leaf. Then . Generating functions help us here.
The generating function for is

where can be thought of as a place holder. Since the delay at each level of the recusion is independent of the delays at other levels, we can sum the delay by multiplying the generating functions. Thus, the generating function for the cumulative delay is . The coefficient of in is at most . For , this coefficient is at most . For any , there is a such that is at most .

To bound the probability that the cumulative delay exceeds on any branch of the recursion, we sum the individual probabilities
for all of the branches. There are at most *N* branches. Thus, the
sum is at most . For any , there is a such
that this sum is at most .

to .667emto .667em

Mon Jul 22 22:57:44 EDT 1996