what will be time complexity of relation T(n)=nT(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

The function is called

n*f(n-1)

times. Replacing f(n-1) with this definition gives

n*((n-1)*f(n-2)

Replacing again gives:

n*((n-1)*((n-2)*f(n-3)))

Removing brackets:

n*(n-1)*(n-2)*...(1)

This gives:

n= 3: 3*2*1 = 6
n= 4: 4*3*2*1 = 24
n= 5: 5*4*3*2*1 = 120

which is n!.

Answer 2

We can list out a few terms

T(0) = 0
T(1) = 1 * 0 + 1
T(2) = 2 * 1 + 2 = 4
T(3) = 3 * 4 + 3 = 15
T(4) = 4 * 15 + 4 = 64
...

We can note a couple of things. First, the function grows more quickly than n!; it starts out smaller than it (at n=0), catches up (at n=1) and surpasses it (at n>=2). So we know that a lower bound is n!.

Now, we need the upper bound. We can notice one thing: T(n) = nT(n-1) + n < nT(n-1) + nT(n-1) for all sufficiently large n (n >= 2, I think). But we can easily show that T(n) = nT(n-1) is a recurrence relation for n!, so we know that a recurrence relation for T(n) = nT(n-1) + nT(n-1) = 2nT(n-1) is (n!)(2^n). Can we do better?

I propose that we can. We can show that for any c > 0, T(n) = nT(n-1) + n < nT(n-1) + cnT(n-1) for sufficiently large values of n. We already know that T(n-1) is bounded below by (n-1)!; so, if we take c = n/(n-1)! we recover exactly our expression and we know that an upper bound is (c^n)(n!). What is the limit of c as n goes to infinity? 0. What is the maximum value assumed by [n/(n-1)!]^n?

Good luck computing that. Wolfram Alpha makes it fairly clear that the maximum value assumed by this function is around 5 or 6 for n ~ 2.5. Assuming you are convinced by that, what's the takeaway?

n! < T(n) < ~6n! for all n. n! is the Theta-bound for your recurrence.

Answer 3

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