Time complexity of functions that call each other

Question

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?

Answer 1

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.

Answer 2

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.