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

Question

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.

Accepted Answer