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?

• quicksort: 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?
• Mike Sweeney: @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.

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.

• Mike Sweeney: 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?
• quicksort: @MikeSweeney: answer edited.

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.

• Mike Sweeney: 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.
• David Richerby: Note that $\geq\Theta(f)$ is just $\Omega(f)$.
• gnasher729: 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.
• gnasher729: The result can easily be calculated in O(n) if you replace foo (x-1)+f(x-1) with 2*f(x-1).