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)

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

  • 1
    $\begingroup$ I think the question needs some clarification. $\endgroup$ – Kaveh Jun 9 '12 at 7:28
  • 1
    $\begingroup$ 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? $\endgroup$ – Raphael Jun 9 '12 at 8:41
  • $\begingroup$ 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. $\endgroup$ – raarava Jun 10 '12 at 17:48
  • $\begingroup$ 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. $\endgroup$ – Raphael Jun 11 '12 at 10:37
  • $\begingroup$ @Raphael: The base case for every running time recurrence is $T(n) \le SomeConstant$ for all $n \le SomeOtherConstant$. $\endgroup$ – 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?

  • $\begingroup$ 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"? $\endgroup$ – Raphael Jun 11 '12 at 14:46
  • 3
    $\begingroup$ 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. $\endgroup$ – JeffE Jun 11 '12 at 15:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.