- #1
ZERO_COOL
- 17
- 0
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 :(