<p>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. </p>

<p>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</p>

<p>$$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
$$</p>

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

<p>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</p>

<p>$$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
$$</p>

<p>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.</p>

CC BY-SA 3.0
2011-12-07T21:28:34.203Z
2011-12-07T21:28:34.203Z
David Harris
<p>Here is a proof that this algorithm runs in $O(n\,m)$ time in expectation and with high probability.</p>

<p>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)\}$.</p>

<p><strong>Lemma 1.</strong> <em>For this modified algorithm, regardless of the random choices of the algorithm, the time is always $O(n\,m)$.</em></p>

<p><em>Proof.</em>  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.</p>

<p>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)$.)</p>

<p>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.</p>

<p>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 &gt;= 2$.)</p>

<p>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 <em>leaf</em> 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.)</p>

<p>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$.</p>

<p>This proves Lemma 1.</p>

<p><strong>Corollary:</strong> <em>The original algorithm runs in $O(n\,m)$ time in expectation.</em></p>

<p><em>Proof.</em> If partition chooses $k=1$, it just duplicates the rectangle.  Since $n&gt;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</p>

<p><strong>Corollary.</strong> <em>The bound also holds with high probability (assuming both $n$ and $m$ tend to infinity).</em></p>

<p><em>Proof sketch.</em> 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$.</p>

<p>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</p>

<hr>

<p>As an aside: <em>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.</em></p>

<p><em>Proof.</em> First note that the total time would be proportional to the sum of the <em>areas</em> 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.  </p>

<p>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</p>

<p>(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.)</p>

CC BY-SA 3.0
2012-11-07T08:24:59.717Z
Thank you very much, this is really interesting and clever idea. Just for a side note, we can use your idea for partitioning d-dimensional array. Just about the part you said children are making $K\times K$ grid, actually they divide the parent in $K^2$ part of rectangles, not necessary same size parts, so they wont make a grid, but still your $2/3$ argument holds about perimeters of parent over total children. Also I couldn't get how if we replace $O(m+n)$ with $O(mn)$ as extra cost of each run, still we have $O(mn)$ total running time. Again thank you very much for very clever idea.
Saeed
CC BY-SA 3.0
2012-11-07T16:13:26.203Z
You're welcome!  I'll edit the proof to clarify the points you raise..
Neal Young
CC BY-SA 3.0
2012-11-07T17:57:43.117Z
Nice clarification and good question in the end, many thanks.
Saeed
CC BY-SA 3.0
2012-11-02T18:55:39.173Z
2012-11-07T17:45:48.233Z
2012-11-07T17:45:48.233Z
Neal Young
<p>Consider the following algorithm, where $c$ is a fixed constant.</p>

<pre><code>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.
}
</code></pre>

<p>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.</p>

<p>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  <em>random</em> number of parts with <em>random</em> sizes.  (As usual, "random" is shorthand for "uniformly at random".)  How does one analyze such an algorithm?</p>

CC BY-SA 3.0
2011-12-06T15:06:04.557Z
Your algorithm called partition is of type $'a$ list -> $'a$ list -> void, but it seems to me that in your last call of the algorithm it has type $'a$ -> $'a$ -> void? Am I misunderstanding something?
Gopi
CC BY-SA 3.0
2011-12-06T15:21:16.757Z
@Gopi, edited with added sample, if is ambiguous, please let me know to make it more readable.
Saeed
CC BY-SA 3.0
2011-12-06T15:47:05.597Z
Thanks :). I misread your algorithm thinking lst1 was the first list.
Gopi
CC BY-SA 3.0
2011-12-06T17:40:29.370Z
The question is poorly written, but underneath it there's a genuine question about analyzing randomized recurrences.
Suresh Venkat
CC BY-SA 3.0
2011-12-07T10:56:19.593Z
Major edit.  Hopefully I've preserved the sense of the question.
Jeffε
CC BY-SA 3.0
2011-12-07T18:57:33.907Z
@JɛﬀE now you should answer it :)
Suresh Venkat
CC BY-SA 3.0
2011-12-08T16:55:18.200Z
Have you looked at the Chaudhuri-Dubhashi paper on probabilistic recurrences (this develops further Karp's original work on this problem): http://www.sciencedirect.com/science/article/pii/S0304397596002617
Suresh Venkat
CC BY-SA 3.0
2012-11-08T22:26:20.037Z
Fixed min(c,n) to min(c,m,n).
Jeffε
<cc.complexity-theory><ds.algorithms><randomness><randomized-algorithms><recursive>
How to analyze a randomized recursive algorithm?
Saeed
# How to analyze a randomized recursive algorithm?

(Asked by: username_0 on 2011-12-06)

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?

**Tags:** cc.complexity-theory, ds.algorithms, randomness, randomized-algorithms, recursive

> **Comments:**
> **username_1**: Your algorithm called partition is of type $'a$ list -> $'a$ list -> void, but it seems to me that in your last call of the algorithm it has type $'a$ -> $'a$ -> void? Am I misunderstanding something?  
> **username_0**: @username_1, edited with added sample, if is ambiguous, please let me know to make it more readable.  
> **username_1**: Thanks :). I misread your algorithm thinking lst1 was the first list.  
> **username_2**: The question is poorly written, but underneath it there's a genuine question about analyzing randomized recurrences.  
> **username_3**: Major edit.  Hopefully I've preserved the sense of the question.  
> **username_2**: @JɛﬀE now you should answer it :)  
> **username_2**: Have you looked at the Chaudhuri-Dubhashi paper on probabilistic recurrences (this develops further Karp's original work on this problem): http://www.sciencedirect.com/science/article/pii/S0304397596002617  
> **username_3**: Fixed min(c,n) to min(c,m,n).  

---

## 2 answers

### Answer by username_5 on 2012-11-02. Score: 9 | Accepted answer

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

> **Comments:**
> **username_0**: Thank you very much, this is really interesting and clever idea. Just for a side note, we can use your idea for partitioning d-dimensional array. Just about the part you said children are making $K\times K$ grid, actually they divide the parent in $K^2$ part of rectangles, not necessary same size parts, so they wont make a grid, but still your $2/3$ argument holds about perimeters of parent over total children. Also I couldn't get how if we replace $O(m+n)$ with $O(mn)$ as extra cost of each run, still we have $O(mn)$ total running time. Again thank you very much for very clever idea.  
> **username_5**: You're welcome!  I'll edit the proof to clarify the points you raise..  
> **username_0**: Nice clarification and good question in the end, many thanks.  

---

### Answer by username_4 on 2011-12-07. Score: 4

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.


---

