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);
}
```
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this communityWhat 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);
}
```
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.