Recurrence driving me crazy

Math and Physics Programming

Started by theMadHatter October 13, 2010 08:25 AM

4 comments, last by theMadHatter 13 years, 6 months ago

154

Author

October 13, 2010 08:25 AM

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?

apatriarca

2,365

October 13, 2010 09:15 AM

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!

theMadHatter

154

Author

October 13, 2010 09:33 AM

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.

apatriarca

2,365

October 13, 2010 09:38 AM

Yes, it looks right to me then.

alvaro

21,604

October 13, 2010 08:10 PM

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

theMadHatter

154

Author

October 14, 2010 09:31 AM

Thank you very much.
That's pretty clever.

Recurrence driving me crazy

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Recurrence driving me crazy

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines