Why is the time complexity for this O(n)?-CodePudding

I am looking at this question:

Let T(n) be the maximum stack depth of the following function, in terms of n.
double foo (int n)
{
    int i;
    double sum;
    if (n == 0) 
        return 1.0;
    else {
        sum = 0.0;
        for (i = 0; i < n; i  )
            sum  = foo (i);
        return sum;
    }
}
Find T(n) = O(?)

The answer provided is O(n), but I calculated to be O(n!). I am not sure how to devise a solution for this.

CodePudding user response：

Stack depth can be expressed as the maximum number of recursive calls down from a single recursion at some point. foo(n) calls foo(0), foo(1),foo(2),..., foo(n - 1). If you trace recursive calls from foo(n-1), you'll see it calls foo(n - 2). It goes like this until f(0) is called. Therefore maximum stack depth is O(n). It's not O(n!).

What about time complexity?

T(n) = T(n-1)   T(n-2)   ...   T(1)   T(0)
T(1) calls T(0) 1 times.  (2^0)
T(2) calls T(0) 2 times.  (2^1)
T(3) calls T(0) 4 times. (from T(2)   T(1)   T(0))
T(4) calls T(0) 8 times.
T(5) calls T(0) 16 times. (2^4)
         ...
T(n-1) calls T(0) 2^(n-2) times.

In total T(0) is called [1   2   4   8   ...   2^(n-2)]   1 times.

It is equal to 2^(n-2) 2^(n-2), which can be expressed as 2^n / 2. Therefore it has exponential time complexity, that is O(2^n).