Recurrence Relation Homework Struggles
-
27-10-2019 - |
题
Here's the question:
Solve the recurrence by obtaining a theta bound for T(n) given that T(1) = theta(1).
T(n) = n + T(n-3)
Attempted Solution:
T(n) = T(n-6) + (n-3) + n
= T(n-9) + (n-6) + (n-3) + n
= T(n-(n-1)) + [(n-n) + (n-(n-3)) + (n-(n-6)) + ... + n]
= T(1) + [0 + 3 + 6 + ... + n]
= theta(1) = 3[1 + 2 + 3 + ... + n/3]
= theta(1) + [(n/3)(n/3 + 1)]/2
= theta(1) + (n^2+3n)/6
When I double check to see if the solution fits the recurrence, it doesn't work.
解决方案
The issue was that you were getting the wrong summation. It doesn't start at 0, since your last T function was T(n - (n-1)) , which means previous one was T(n-(n-4)). So the summation starts at 4, and goes up till n.
If you don't know how to find the summation of this, I'd suggest you look at some of the proofs from the summation formula. This is what the solution looks like.
T(n) = T(n-3) + n
= T(n-6) + (n-3) + n
= T(n-(n-1)) + [ (n-(n-4)) + (n-(n-7)) + ... + n]
= T(1) + [4 + 7 + ... + n]
= theta(1) + (4 + n) * (n - 1)/6
不隶属于 StackOverflow