1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Solving recurrence systems

  1. May 14, 2010 #1
    1. The problem statement, all variables and given/known data
    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)


    3. 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 :(
     
  2. jcsd
  3. May 14, 2010 #2

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    That is the correct formula.

    Have you tried to prove it via induction? (That is a big fat hint).
     
  4. May 14, 2010 #3
    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?
     
  5. May 14, 2010 #4

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    You are trying too hard. Try induction. How are you going to prove this by any means other than by induction?
     
  6. May 14, 2010 #5
    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.
     
  7. May 14, 2010 #6

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    You have a guess, aka a hypothesis. You can use induction to prove or disprove this hypothesis.
     
  8. May 15, 2010 #7
    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,
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook