Return to Answer

As an aside: if the algorithm were to choose $k$ randomly in $\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.

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.

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 with $k$ at least 2. Of course each rectangle's corners have only integer coordinates.

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

As an aside, if the algorithm were to choose $k$ in $\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 and with high probability.

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.

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

As an aside: if the algorithm were to choose $k$ randomly in $\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.)

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| = O(nm)$$ 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).

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