# Time complexity of similar-looking functions

What is the time complexity of the following functions, and why?

int f(int n)
{
if (n <= 1) return n;
return 2*f(n-1);
}

int g(int n)
{
if (n <= 1) return n;
return g(n-1) + g(n-1);
}
$$$$

• You might be wondering whether they have the same time complexity or not. Try writing the recurrence relation for the run times for both of them. – Jamāl Jan 26 at 9:05
• Rather than suggesting a code layout fix, I ask you to present both implementations as pseudocode. – greybeard Jan 26 at 11:18
• Does this answer your question? Is there a system behind the magic of algorithm analysis? – xskxzr Jan 27 at 1:50
• I think you have all missed the point of this question. See my answer. – Yuval Filmus Jan 30 at 10:17

## 1 Answer

The answer is actually subtler than it looks.

Let us first consider a naive compiler. This naive compiler will implement the recursive case of $$g$$ by actually running $$g(n-1)$$ twice. The recurrences for the running time will be \begin{align*} T_f(n) &= T_f(n-1) + O(1) & T_f(1) &= O(1), \\ T_g(n) &= 2T_g(n-1) + O(1) & T_g(1) &= O(1), \end{align*} whose solutions are $$T_f(n) = O(n)$$ and $$T_g(n) = O(2^n)$$.

Usually we allow the compiler to perform some optimizations. It could potentially optimize the calculation of $$g(n-1) + g(n-1)$$ by first computing $$x = g(n-1)$$, and then calculating $$x + x$$ or $$2x$$ (or potentially $$x \ll 1$$). However, this should be done with care, since it could have modified the semantics of the program. Suppose for example that we modify the code by adding side-effects:

int fx(int n)
{
printf("x");
if (n <= 1) return n;
return 2*fx(n-1);
}

int gx(int n)
{
printf("x");
if (n <= 1) return n;
return gx(n-1) + gx(n-1);
}


In this case $$fx(2)$$ results in printing $$xx$$ while $$gx(2)$$ results in printing $$xxx$$. Therefore an optimizer cannot convert $$gx$$ into $$fx$$, though it could convert $$g$$ to $$f$$. A smart optimizer will be able to detect, using static analysis, that there are no side effects in $$g$$, and so convert $$g$$ to $$f$$.

I tried it out with clang version 12.0.0. Without any optimizations (-O0), the function $$g$$ has two recursive calls. With optimizations (-O1` and higher), the code of $$g$$ becomes identical to the code of $$f$$. The code of $$gx$$ is of course unaffected.