Sign in to follow this  

Recurrence driving me crazy

Recommended Posts

theMadHatter    154
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 < n
And here we can use m = n - 1
Which yields T(n - 1) <= c(n-1)!
Plugging this back in to the recurrence gives us
T(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 this post

Link to post
Share on other sites
apatriarca    2365
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 this post

Link to post
Share on other sites
theMadHatter    154
Yes, so for the first part.

At T(6) the hypothesis T(n) <= cn! holds:
T(1) = 1
T(2) = 3 2! = 2
T(3) = 9 3! = 6
T(4) = 31 4! = 24
T(5) = 129 5! = 120
T(6) = 651 6! = 720
T(6) <= 6!

As for the other thing

cn! - c(n-1)! + n <= cn!
Written another way
cn! <= cn! + c(n-1)! - n
This is true whenever
c(n-1)! >= n
Which is the case when n >= 6 and c >= 1 which is our base case.

Share this post

Link to post
Share on other sites
alvaro    21266
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 this post

Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this