Time complexity of functions that call each other 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 &lt; 1) return 1;
  else return foo(x-1) + bar(x);
}

int bar(int x)
{
  if(x &lt; 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?
To help with your intuition, change the code by substituting the code for bar into foo:

int foo(int x)
{
  if(x &lt; 1) return 1;
  else if (x &lt; 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 &lt; 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.