Time complexity of similar-looking functions

Question

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);
}
```

Answer 1

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.