Time Complexity Formula for Solving Recurrence Systems

[ZERO_COOL]

Homework Statement

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)

The Attempt at a Solution

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 :(

 

[D H]

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 :(

That is the correct formula.

Have you tried to prove it via induction? (That is a big fat hint).

 

[ZERO_COOL]

I have guessed at the formula being that it is a fairly simple pattern. I was taught that induction is used to prove a formula is a solution of a recurrence system when you have been given the solution. I'm trying to solve a recurrence system first using this algebraic technique. It's my fault for not explaining correctly I understand why you suggested induction. My problem is in my algebraic technique.

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?

 

[D H]

You are trying too hard. Try induction. How are you going to prove this by any means other than by induction?

 

[ZERO_COOL]

Technically I do not have a formula to prove via induction.

I am trying to work out a formula from the recurrence system.

My goal is not to prove an established formula for a recurrence system but rather establish a formula for a recurrence system.

So when I am able to establish a formula from the recurrence system I will then be able to prove it is correct by using induction.

What I'm trying to achieve is using algebra solve a recurrence system.

Until I'm able to solve the recurrence system I am not able to prove the formula because there is no formula.

 

[D H]

You have a guess, aka a hypothesis. You can use induction to prove or disprove this hypothesis.

 

[ZERO_COOL]

I've used induction to get the formula as T(n) = 5n + 4.

Classifying this as O(f(n)) for a suitable function of f in the Big Oh hierarchy I get.

f(n) = 5n + 4 = O(n). This is because n is the dominant term.

I'm pretty sure on this just need a quick nod of approval if possible.

Thanks,