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: Solve the recurrence: t(n) = t(n/2) + n + 2 (Solution included).

  1. Apr 25, 2012 #1


    User Avatar

    1. The problem statement, all variables and given/known data
    The problem along with its solution is attached as Problem.jpg.

    2. Relevant equations
    Recurrence relation.

    3. The attempt at a solution
    I am confused as to what the solution is stating. I get up to and including (3) but I am stuck at (4). After (4), I get that k = log2(n) because n = 2^k = 2^(log2(n)) = n.

    I would greatly appreciate it if someone could help me get unstuck!
    Thanks in advance!

    Attached Files:

    Last edited: Apr 25, 2012
  2. jcsd
  3. Apr 25, 2012 #2
    You forgot to attach Problem.jpg.
  4. Apr 25, 2012 #3


    User Avatar

    Lol. Thanks for telling me.
  5. Apr 26, 2012 #4


    User Avatar

    Staff: Mentor

    Seems there is a "+" sign missing in (4). koZTB.gif

    It should be t(n/2k) + n + n/2 + ....

    Then in going from (5) to (6), make use of the fact that
    n/2k-1 ≡ n/(2k/2)
       ≡ 2n/2k, but k=log2n
       ≡ 2n/n
       ≡ 2 
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook