Is the following recurrence for this program's runtime correct?

Question

Let $f$ and $g$ be two functions and $p$ a number. Consider the following program:

Recurs(v,p) :
  find s < v such that f(s,v) < v/2 and g(s,v-s) < p

  if no such s exists then
    return v
  else if s <= v/4 then 
    return v-s U Recurs(s,p)
  else if s > v/4 then 
    return Recurs(s,p) U Recurs(v-s,p)
end

Can the recurrence for the running time of this recursion be $T(v)=T\left(\frac{v}{4}\right)+T\left(\frac{3v}{4}\right)+1$?

Answer 1

tl;dr: NO. Well, okay, maybe.

Translating the pseudocode mechanically into a recurrence gives me $$ T(n) = \Theta(1) + F(n) + \max \begin{cases} \max_{0\le s \le n/4} T(s) \\ \\ \max_{n/4 < s < n} (T(s) + T(n-s)) \end{cases} $$ where $F(n)$ is the time for the first "find" step. Every outcome that is not known in advance is folded into the $\max$; since we're bounding the worst-case running time, we always assume the worst possible outcome. The initial $\Theta(1)$ includes all the time for bookkeeping, comparisons, stack manipulation, and that union operation in the output. (Performing a set union in constant time is somewhat magical, but I'll let that slide.) I'm also assuming here that the variable $s$ always lies between $0$ and $v-1$, since otherwise the algorithm never terminates, although this assumption is never specified in the code.

Under the reasonable assumption that $T(n)$ is monotonically increasing, we have $$ \max_{0\le s \le n/4} T(s) = T(n/4) $$ Under the further assumption that $T(n)$ is "nice" and convex, we have $$ \max_{n/4 < s < n} (T(s) + T(n-s)) = \begin{cases} T(n-1) + T(1) & \text{if $T$ is convex}\\ T(n/4+1) + T(3n/4-1) & \text{if $T$ is concave} \end{cases} $$ Here, "convex" means that $(T(a) + T(b))/2 \ge T((a+b)/2)$ for all $a$ and $b$, or less formally, that the function "curves upward". If $T$ is "nice", this is equivalent to assuming $T(n) = \Omega(n)$. Symmetrically, $T$ is concave (curves downward) iff $T(n) = O(n)$.

("Nice" means a function whose second derivative is well-defined and doesn't oscillate between positive and negative forever; for example, the product of a polynomial and some logarithms is nice. Wacky functions like $n^{2 + \sin(2\pi n)}$ are not nice, but I'll bet you a dollar that your algorithm doesn't have that function as a time bound.)

So our recurrence is now $$ T(n) = \Theta(1) + F(n) + \max\begin{cases} T(n/4) \\ T(n-1) + T(1) \\ T(n/4 + 1) + T(3n/4 - 1) \end{cases} $$ If $T$ is increasing, the first case is smaller than the other two, so we can ignore it. So we have two possibilities to consider.

First, suppose $$ T(n) = \Theta(1) + F(n) + T(n-1) $$ (I folded the extra $T(1)$ into the $\Theta(1)$ term.) This recurrence unrolls into a simple summation $$ T(n) = \Theta(n) + \sum_{i=1}^n F(i) $$ which implies that $T(n)$ is convex no matter what function $F(n)$ is. So this recurrence seems to work. (The apparently circular argument about convexity can be unwound into a boring and mechanical proof by induction, if you care.)

On the other hand, suppose $$ T(n) = \Theta(1) + F(n) + T(n/4 + 1) + T(3n/4 - 1). $$ Then even with the very strong assumption that $F(n) = O(1)$, a quick recursion tree argument implies that $T(n) = \Theta(n)$. The same recursion tree argument implies that if $F(n)$ is grows even slightly faster than a constant, then $T(n)$ is strictly convex, which means this is the wrong recurrence.

So this recurrence only works when $F(n) = O(1)$. In that case, we can simplify the recurrence further to $$ T(n) = \Theta(1) + T(n/4 + 1) + T(3n/4 - 1). $$ We still have those pesky off-by-ones in the recursive arguments, but whatever. We've already figured out that $T(n) = \Theta(n)$, so who cares about the recurrence any more?