CODEWITHSUNDEEP
algorithmtime-complexity
cx2106qz
cx2106qz

Reputation: 3

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

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.

Upvotes: 0

Views: 110

Answers (1)

Muhteva
Muhteva

Reputation: 2832

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).

Upvotes: 1

Related Questions