How to analyze a randomized recursive algorithm?

Question

Consider the following algorithm, where $c$ is a fixed constant.

void partition(A[1..m], B[1..n])
{
   if m=1 or n=1
      return

   k = random(min(c,m,n));
   partition A into k sublists Asub[1..k] at k-1 distinct random indices
   partition B into k sublists Bsub[1..k] at k-1 distinct random indices

   for i = 1 to k
     for j = 1 to k
        partition(Asub[i], Bsub[j])

   Do something that takes O(n+m) time.
}

What is the expected running time of this algorithm? The running time appears to be $O(mn)$, but I can't find the proof for this.

If we instead partitioned the input lists into $k$ different parts of equal length, we would have the recurrence $T(n,m) = k^2\,T(n/k,m/k) + O(n+m)$ with base case $T(1,n) = T(m,1) = O(1)$; it is not hard to prove that $T(n,m) = O(mn)$. But the algorithm partitions the input into a random number of parts with random sizes. (As usual, "random" is shorthand for "uniformly at random".) How does one analyze such an algorithm?

Answer 1

Here is a proof that this algorithm runs in $O(n\,m)$ time in expectation and with high probability.

First consider the algorithm modified so that $k$ is chosen in $\{2,3,..,\min(c,n)\}$ instead of randomly in $\{1,2,...,\min(c,n)\}$.

Lemma 1. For this modified algorithm, regardless of the random choices of the algorithm, the time is always $O(n\,m)$.

Proof. Fix an input $A[1..n]$ and $B[1..m]$ and fix the random choices of the algorithm arbitrarily. In each (possibly recursive) call to partition(), the two arguments correspond respectively to two subarrays: a subarray $A[i_1..i_2]$ of $A$ and a subarray $B[j_1..j_2]$ of $B$. Identify such a call with the rectangle $[i_1-1,i_2] \times [j_1-1,j_2]$. Thus, the top-level call is $[0,n]\times[0,m]$, and each recursive call corresponds to a sub-rectangle within this $n\times m$ rectangle. These rectangles form a tree, where the rectangle corresponding to one call has as children the rectangles that correspond to the calls made directly by that call. Each parent rectangle is partitioned by its child rectangles, which form a $k\times k$ grid (of non-uniform rectangles) with $k$ at least 2. Of course each rectangle's corners have only integer coordinates.

The running time of the algorithm is bounded by a constant times the sum, over the rectangles, of the perimeters of all of these rectangles. (This is because the time within each call is O(n+m), and the perimiter of the corresponding rectangle is $2(n+m)$.)

I claim that in any set of rectangles as described above, the sum of the perimeters is at most $12 n\,m$. If true, this proves the lemma.

To prove the claim, observe first that, because $k \ge 2$, for any parent rectangle, the perimeter of the parent is at most 2/3 times the total perimeter of the children. (The perimeter of the parent is $2(n+m)$. The total perimiter of the children is $(1+k)(n+m)$, and $k >= 2$.)

It follows by a standard charging argument that the total perimiter of all the rectangles is at most $(1 + 2/3 + (2/3)^2 + \ldots ) = 3$ times the perimiter of just the leaf rectangles. (The observation implies that $P_N \le (2/3) P_T$, where $P_N$ is the total perimeter of the non-leaf rectangles and $P_T$ is the total perimeter of all the rectangles. This implies $P_T \le 3(P_T-P_N)$, and $P_T-P_N$ is the total perimeter of the leaf rectangles.)

Next, observe that the leaf rectangles partition the original $n\times m$ rectangle. The maximum possible perimeter of the leaves is obtained when the leaves correspond to the unit squares with integer endpoints, in which case the total perimeter of the leaves is $4\,n\,m$. Thus, the sum of the perimeters is at most $3\cdot 4\,n\,m$, that is, at most $12 n\,m$.

This proves Lemma 1.

Corollary: The original algorithm runs in $O(n\,m)$ time in expectation.

Proof. If partition chooses $k=1$, it just duplicates the rectangle. Since $n>1$, the probability that $k=1$ is at most 1/2. Thus, the expected number of times each rectangle is duplicated is at most 1 (and the expected number of copies of each rectangle is at most 2). Thus, for the original algorithm, the expected sum of the perimiters of all the rectangles is at most twice that of the modified algorithm, i.e. at most $24 n\,m$. Just as in the analysis of that algorithm, the running time is proportional to this sum, so is $O(n\,m)$. QED

Corollary. The bound also holds with high probability (assuming both $n$ and $m$ tend to infinity).

Proof sketch. Fixing every random choice except the number of duplicates of each rectangle, the time is proportional to $$\sum_{r\in R} (1+X_r) |r|$$ where $R$ is the set of rectangles generated, $X_r$ is the number of times $r$ is duplicated (i.e., times when $k=1$ for that rectangle), and $|r|$ is the perimeter of $r$.

The variables $\{X_r : r \in R\}$ are independent, and each $|r|$ is $O(n+m) = o(n m)$, so by a standard Chernoff bound, the probability that the sum exceeds twice its expectation is $o(1)$. (More specifically, take $Y_r = (1+X_r) |r|/2(n+m)$, then apply Chernoff to the sum of the $Y_{r}$'s.) QED

---

As an aside: if the algorithm were to choose $k$ randomly up to $\min(n,m)$ instead of $\min(c,n)$ and then do $O(m n)$ work in each call (instead of $O(m+n)$), the total time would still be $O(mn)$ in expectation.

Proof. First note that the total time would be proportional to the sum of the areas of all the rectangles. This sum equals the sum, over the integer coordinates $(i,j)$, of the number of rectangles that $(i,j)$ occurs in. This is $O(nm)$ in expectation because, in expectation, any given $(i,j)$ in the original rectangle occurs in $O(1)$ rectangles.

To see this, suppose $(i,j)$ is contained in a rectangle $r$, and consider the call to partition on $r$. Let $q(r) = \min(n_r,m_r)$. Let $r'$ be the rectangle that is the child (containing $(i,j)$) of $r$. With probability at least $1/3$, $k$ is chosen to be at least $(2/3)q(r)$. Conditioned on that, $E[q(r')] \le 3/2$, so with constant probability $q(r')$ is at most 1. If that happens, then $r'$ is a leaf (has no children). It follows from this that the expected number of rectangles that $(i,j)$ is in is $O(1)$. QED

(Whether the $O(nm)$ bound would hold with high probability is an interesting question.. I think it would. Certainly $O(nm\log(nm))$ would hold w.h.p.)

Answer 2

The typical approach is to analyze the expected value of the running times of the algorithm. In this case, the expected value of the running time, on any problem with $m,n$, is something like $k^2$ times the expected running time of the subproblems partition[$A_i,B_j$]. For each $i,j$ the size of the subproblem is a random variable.

The length of the list $A_i$ is the difference between the $i$th and $i+1$th order statistics when $k$ elements are drawn u.a.r from $\{1, ..., m \}$. This is essentially $m \beta(k,m+k+1)$ (i.e. is $m$ times a draw from a $\beta(1,m+k+1)$ random variable). Hence we have

$$T[m,n | k] = C (m + n) + k^2 \int_{x,y} T(m x, n y) \frac{x^{k-1} y^{k-1} (1-x)^{m+k-1} (1-y)^{n+k-1}}{\beta(k,n+k+1) \beta(k,m+k+1)} dx dy $$

There is some rounding error here, as we should really have $T(\lceil mx \rceil, \lceil ny \rceil)$ in the integrand.

Unfortunately $k$ is a random variable so one must also integrate over it. I don't think there is any point to requiring $k \leq n$, as if $k \geq n$ you will simply partition the data into a sub-lists which may be empty. So say $k$ is chosen uniformly at random from $1,\dots, c$. Then you obtain

$$T[m,n] = C (m + n) + \sum_{k=1}^c \frac{k^2}{c} \int_{x,y} T(m x, n y) \frac{x^{k-1} y^{k-1} (1-x)^{m+k-1} (1-y)^{n+k-1}}{\beta(k,n+k+1) \beta(k,m+k+1)} dx dy $$

This recurrence is pretty horrible, but if you have a guess for a bound on $T[m,n]$ (I suppose $T(m,n) = O( (\log m + \log n) (m+n) )$ ) you can plug it in and verify it.