# Recurrence driving me crazy

This topic is 2686 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hello all,
I'm looking into the solution to this recurrence

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

I'm about 90% sure that O(n!) is the correct answer except I'm having real trouble wrapping my head around a proof.

I can use the substitution method in this manner:
Guess that T(n) = O(n!)This implies that T(n) <= cn!From here we assume T applies to m < nAnd here we can use m = n - 1Which yields T(n - 1) <= c(n-1)!Plugging this back in to the recurrence gives usT(n) <= (n-1)*c(n-1)! + n     <= (nc - c)(n-1)! + n     <=  nc(n-1)! - c(n-1)! + n     <=  cn! - c(n-1)! + n     <=  cn!Reduction to last line works when c >= 1

This works , right?

##### Share on other sites
I always called this method as mathematical induction. You missed the first step of the proof where you have to prove there is some value k for which the thesis is true and in the second step of the proof, I'm not convinced by
T(n) <=  cn! - c(n-1)! + n     <=  cn!

##### Share on other sites
Yes, so for the first part.
At T(6) the hypothesis T(n) <= cn! holds:T(1) = 1T(2) = 3       2! = 2T(3) = 9       3! = 6T(4) = 31      4! = 24T(5) = 129     5! = 120T(6) = 651     6! = 720T(6) <= 6!

As for the other thing
cn! - c(n-1)! + n <= cn!Written another waycn! <= cn! + c(n-1)! - nThis is true wheneverc(n-1)! >= nWhich is the case when n >= 6 and c >= 1 which is our base case.

##### Share on other sites
Yes, it looks right to me then.

##### Share on other sites
You can improve to O((n-1)!). In order to prove that, define

C(n) := T(n)/(n-1)!

We can find a recurrence for C(n) like this:

C(n) = T(n)/(n-1)!
= ((n-1)*T(n-1) + n)/(n-1)!
= (n-1)*(n-2)!*C(n-1)/(n-1)! + n/(n-1)!
= C(n-1) + n/(n-1)!

So C(n) is just the n-th partial sum of the sequence n/(n-1)!. Since the sum converges, it means that C(n) is bounded, so C(n) = O(1) and T(n) = O((n-1)!).

##### Share on other sites
Thank you very much.
That's pretty clever.