Now is not clear what the pattern is?
Solve the recurrence system below and dtermine a formula for the time complexity function T(n).
T(0) = 4.
T(n) = 5 + T(n - 1) (n > 0)
My effort at solving is below...
T(3) = 5 + T(2).
T(2) = 5 + T(1).
T(1) = 5 + T(0).
T(3) + T(2) + T(1) = 3 * 5 + T(2) + T(1) + T(0)
T(3) = 3 * 5 + T(0)
T(3) = 15 + 4.
Now try to obtain a formula for T(n) in terms of n.
T(n) = 5 + T(n - 1).
T(n - 1) = 5 + T(n - 2).
T(1) = 5 + T(0).
T(0) = 4.
T(n) + T(n - 1) + T(1) + T(0) = 3 * 5 + T(n - 1) + T(n - 2) + T(0) + 4.
**THIS IS WHERE MY BRAIN HITS MELTING POINT AND THE COOLANT IS RELEASED.
I'm pretty sure the formula should be T(n) = 5 * n + 4. So,
T(0) = 5 * 0 + 4 = 4
T(3) = 5 * 3 + 4 = 19.
I need to prove it though
How does this look below:-
Now try to obtain a formula for T(n) in terms of n.
T(n) = 5 + T(n - 1).
T(n - 1) = 5 + T(n - 2).
T(2) = 5 + T(1)
T(1) = 5 + T(0).
T(0) = 4.
Sum each side and equate result...
T(n) + T(n - 1) + T(2) + T(1) + T(0) = T(n - 1) + T(n - 2) + T(1) + T(0) + 4 + (n - 1) * 5 + 4.
Subtract terms that appear on both sides...
T(n) = (n - 1) * 5 + 4 = 5n - 5 + 4 = 5n + 4 = 4 + 5n.
I'm a bit dubious about my algebra above, I feel like I'm close, I can taste it. Is it close / correct?
Well I would hope that after reading these posts and thinking about them, you will no longer be "pretty sure" but rather 100% sure that the solution is T(n) = 5n + 4.
As for proof, if you're comfortable with inductive proofs, this one is very easy. Using mathematical induction is the typical way to prove these kinds of things.
Problem is I need to use algebra to arrive at the formula rather than guessing and then using induction to prove it. Thats why I'm hoping someone can check my,
T(n) = 5 + T(n - 1).
T(n - 1) = 5 + T(n - 2).
T(2) = 5 + T(1)
T(1) = 5 + T(0).
T(0) = 4.
Sum each side and equate result...
T(n) + T(n - 1) + T(2) + T(1) + T(0) = T(n - 1) + T(n - 2) + T(1) + T(0) + 4 + (n - 1) * 5 + 4.
Subtract terms that appear on both sides...
T(n) = (n - 1) * 5 + 4 = 5n - 5 + 4 = 5n + 4 = 4 + 5n.
Thus T(n) = 4 + 5n
There is no guessing involved. You can see that the expression is T(n) = 5n + 4 if you just look hard enough.
It's like this sequence:
a(0) = 1
a(n) = 2*a(n-1), n>0
I can just see that this is a(n) = 2^n and there is absolutely no guessing involved.
Although to be fair, guessing is a valid approach for many of these types of problems.
Where did this last equation come from??? When I sum each side I get
T(n) + T(n - 1) + T(2) + T(1) + T(0) = 5 + T(n - 1) + 5 + T(n - 2) + 5 + T(1) + 5 + T(0) + 4
Your correct, when you sum each side you do get,
T(n) + T(n - 1) + T(2) + T(1) + T(0) = 5 + T(n - 1) + 5 + T(n - 2) + 5 + T(1) + 5 + T(0) + 4
Removing all the terms that appear on both sides, I get,
T(n) + T(2) = 5 + 5 + T(n - 2) + 5 + 5 + 4
Problem is I think I need to get rid of that T(2) term on the right some how??