-2
$\begingroup$

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);
}
```
$\endgroup$
4
  • 1
    $\begingroup$ 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. $\endgroup$ – Jamāl Jan 26 at 9:05
  • 1
    $\begingroup$ Rather than suggesting a code layout fix, I ask you to present both implementations as pseudocode. $\endgroup$ – greybeard Jan 26 at 11:18
  • 1
    $\begingroup$ Does this answer your question? Is there a system behind the magic of algorithm analysis? $\endgroup$ – xskxzr Jan 27 at 1:50
  • $\begingroup$ I think you have all missed the point of this question. See my answer. $\endgroup$ – Yuval Filmus Jan 30 at 10:17
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.