c - what will be time complexity of relation T(n)=nT(n-1)+n

Question

WHAT will be time complexity of relation T(n)=nT(n-1)+n in my prog something like this

f(int n)
{
    c++;
    if(n>0)
        for(i=1;i<=n;i++)
            f(n-1);
}

i took a counter to count how many time function called it gives answer between n to n! thanks.

Answer 1

Your code lacks the +n part of the recursion, so I assume that the code is wrong and the recursion

T(n) = n*T(n-1) + n

is correct.

Let f(n)=T(n)/n!, then

f(n) = T(n)/n! = n(T(n-1)+1)/n! 
     = T(n-1)/(n-1)! + 1/(n-1)!
     = f(n-1) +  1/(n-1)!
     = sum(1,n-1, 1/k!)
     ~ e

Thus T(n) ~ e*n!.