3
$\begingroup$

I'm having trouble reasoning about the time complexity of these mutually recursive functions. This was asked on SO here but the answer there didn't help me. I tried substituting one of the recurrences in the other but because they are mutually recursive I got stuck. I tried writing out the function calls for x=10 but I'm stuck making sense of that too. How do I go about working through something like this?

int foo(int x)
{
  if(x < 1) return 1;
  else return foo(x-1) + bar(x);
}

int bar(int x)
{
  if(x < 2) return 1;
  else return foo(x-1) + bar(x/2);
}

Edit: With @quicksort's answer I get S(n) = 2*S(n-1) + S(n/2) - S(n/2-1) and if I try to solve it using Wolfram I'm seeing something different: solution . Also, it's not intuitive to me that this is exponential. How does one see that?

$\endgroup$
  • $\begingroup$ How does that contradict what I said and what does that Wolfram query have to do with anything at all? (just by the way: don't use Wolfram Alpha for solving recursive equations of complexity, it's a terrible tool). Intuition for exponential running time: Function splits in two. Each recursive call splits in two. Each of them further splits in two... See any pattern? $\endgroup$ – quicksort Jan 18 '17 at 22:13
  • $\begingroup$ @quicksort I wasn't questioning your answer, I'm clearly struggling with this. Based on previous questions I'd seen people recommend using Wolfram so that's why I used it. $\endgroup$ – Mike Sweeney Jan 19 '17 at 3:41
1
$\begingroup$

Let $\mathcal{S}(n)$ be the running time of foo and $\mathcal{T}(n)$ be the running time of bar. We have the following system of recursive equations:

$$ \left\{ \begin{array}{r c l} \mathcal{S}(n) & = & \mathcal{S}(n-1) + \mathcal{T}(n) + \Theta(1)\\ \mathcal{T}(n) & = & \mathcal{S}(n-1) + \mathcal{T}(n/2) + \Theta(1) \end{array} \right. $$

By isolating $\mathcal{T}(n)$ in the first and $\mathcal{S}(n)$ in the second, we obtain:

$$ \left\{ \begin{array}{r c l} \mathcal{S}(n-1) & = & \mathcal{T}(n) - \mathcal{T}(n/2) + \Theta(1)\\ \mathcal{T}(n) & = & \mathcal{S}(n) - \mathcal{S}(n-1) + \Theta(1) \end{array} \right. $$

I will now solve for $\mathcal{T}$, with a similar reasoning holding for $\mathcal{S}$. Since:

$$ \mathcal{S}(n-1) = \mathcal{T}(n) - \mathcal{T}(n/2) + \Theta(1) $$

We also have that:

$$ \mathcal{S}(n) = \mathcal{T}(n+1) - \mathcal{T}((n+1)/2) + \Theta(1) $$

Therefore the first equation of our original system becomes:

$$ \mathcal{T}(n+1) - \mathcal{T}((n+1)/2) = \mathcal{T}(n) + \mathcal{T}(n) - \mathcal{T}(n/2) + \Theta(1) $$

Reordering the terms:

$$ \mathcal{T}(n+1) = 2 \mathcal{T}(n) - \mathcal{T}(n/2) + \mathcal{T}((n+1)/2) + \Theta(1) $$

Since $(n+1)/2$ is either $n/2$ or $n/2+1$, it must be that $$ \mathcal{T}((n+1)/2) - \mathcal{T}(n/2) \ge 0$$

which means:

$$ \mathcal{T}(n+1) \ge 2 \mathcal{T}(n) + \Theta(1) $$

and:

$$ \mathcal{T}(n) \in \Omega(2^n) $$

We can check the other arrow (i.e. $ \mathcal{T}(n) \in \mathcal{O}(2^n) $) by induction.

$\endgroup$
  • $\begingroup$ I'm not sure how to get from either of the system of recurrences to a closed form. Is this abnormally complicated or is there something I'm missing? $\endgroup$ – Mike Sweeney Jan 19 '17 at 7:28
  • $\begingroup$ @MikeSweeney: answer edited. $\endgroup$ – quicksort Jan 19 '17 at 11:08
3
$\begingroup$

To help with your intuition, change the code by substituting the code for bar into foo:

int foo(int x)
{
  if(x < 1) return 1;
  else if (x < 2) return 2; // foo(0) + bar(1), x = 1
  else return foo(x-1) + foo(x-1) + bar(x/2);
}

int bar(int x)
{
  if(x < 2) return 1;
  else return foo(x-1) + bar(x/2);
}

So now it is obvious that T (x) ≥ $Θ(2^x)$, since foo (x) does two recursive calls to foo (x-1). Also makes it obvious that the result is foo (x) ≥ $Θ(2^x)$, and that result can be calculated in linear time.

$\endgroup$
  • $\begingroup$ I think I understand the first part but what if I wanted to get a tighter bound and account for the call to bar(x/2)? Also, I'm not clear what your last sentence regarding the result is and where the linear part is coming into the picture. $\endgroup$ – Mike Sweeney Jan 19 '17 at 7:33
  • $\begingroup$ Note that $\geq\Theta(f)$ is just $\Omega(f)$. $\endgroup$ – David Richerby Jan 19 '17 at 12:11
  • $\begingroup$ The functions return a value - that's the result. You can do the calculation faster. That doesn't change the result. Usually the result is important. $\endgroup$ – gnasher729 Jan 20 '17 at 8:19
  • $\begingroup$ The result can easily be calculated in O(n) if you replace foo (x-1)+f(x-1) with 2*f(x-1). $\endgroup$ – gnasher729 Jan 20 '17 at 8:23

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.