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

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

• I think the question needs some clarification. – Kaveh Jun 9 '12 at 7:28
• 1) A yes-no question, really? 2) You need an anchor. 3) This seems to be a recursion for an upper bound on the depth. 4) You seem to be assuming that $D$ is non-decreasing. 5) Why do you add depths of "parallel" calls? 6) What happens if s = v/4? – Raphael Jun 9 '12 at 8:41
• I corrected the question. It is an yes-no question. I dont think it is an upper bound on depth but it is a recurrence for the time complexity. T (D is renamed to T now) is non-decreasing with v and I mentioned in the program what happens when s=v/4. – raarava Jun 10 '12 at 17:48
• Now it's definitely an upper bound for runtime (modulo the missing anchor, which you'll probably choose as $1$?) provided you don't care at all for constants (what do you count?) and the find ... step is possible in $O(1)$ -- which is unlikely. – Raphael Jun 11 '12 at 10:37
• @Raphael: The base case for every running time recurrence is $T(n) \le SomeConstant$ for all $n \le SomeOtherConstant$. – JeffE Jun 11 '12 at 13:11

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?

• Beware the $=$ that don't stand for equality! I don't get the end, namely "which means this is the wrong recurrence". And where did the case 2 version go, which you identified as "working"? – Raphael Jun 11 '12 at 14:46
• I identified case 1 as a valid recurrence for the worst-case running time of the algorithm, which was the original question. The n/4-3n/4 recurrence is only valid if T is concave, but if $F(n)=\omega(1)$, the recurrence implies T is non-concave, so we have a contradiction. – JeffE Jun 11 '12 at 15:08