Time complexity of functions that call each other
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.