Jump to content
  • Advertisement
Sign in to follow this  
theMadHatter

Recurrence driving me crazy

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

If you intended to correct an error in the post then please contact us.

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 < 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
Advertisement
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
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
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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!