Time complexity of recursive function inside for l

问题:

If we have a function:-

int x=0;

int fun(int n)
{
    if(n==0) 
        return 1;

    for(int i=0; i<n;i++)
        x += fun(i);
}

According to me, time complexity can be calculated as:-

T(n) = T(n-1) + T(n-2) +...+ T(0).
T(n) = nT(n-1).

T(n) = O(n!).

Am I correct?

回答1:

If you're measuring the number of function calls (or additions -- it turns out the same), the correct recurrence relations are:

T(0) = 0
T(n) = T(0) + T(1) + T(2) + ... + T(n-1) + n

You can compute the first few values:

 T(0) = 0
 T(1) = 1
 T(2) = 3
 T(3) = 7
 T(4) = 15

You can guess from this that T(n) = 2^n - 1, and that's easy to check by a proof by induction.

In some sense you are right that T(n) = O(n!) since n! > 2^n for n>3, but T(n) = O(2^n) is a tighter bound.