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: Recurrence Relation Help

  1. Oct 19, 2008 #1
    1. The problem statement, all variables and given/known data
    Solve and prove your solution for the following recurrence relation for the number of comparisons in Binary Search:

    C(21 - 1)=1
    C(2i - 1) = 2 + C(2(i+1) - 1)

    3. The attempt at a solution

    The setup for this would be:

    C(n)={ 1, n=1 and 2 + C(2(i+1) - 1), otherwise

    From this I would do substitution and guessing, and then prove the guess with induction?
  2. jcsd
  3. Oct 19, 2008 #2


    Staff: Mentor

    Are you sure you have your recurrence relation right? Usually the formula for the general term (the i-th term) is given in terms of the previous term, not the next term.
  4. Oct 19, 2008 #3
    I am assuming that is what the teacher wants. Could this be it:

    C(n)={ 1, n=1 and C(n/2) + 2, otherwise
  5. Oct 19, 2008 #4


    Staff: Mentor

    My question is not about what the teacher wants, but instead is about what exactly are you given to work with.

    Clearly C(1) = 1 from the given information.
    What is C(2) though? There is no way to calculate this according to the recurrence relation you show.
    What about C(3)? To get this, you need to know C(7).

    A recurrence relation usually gives a formula for the i-th term in the sequence in terms of the (i - 1)st term, and gives you the 1st term. From the recurrence formula you can work through and get C(2), C(3), C(4), and so on.

    When I said this earlier, you came up with what looks like a different recurrent formula. At this point I'm less interested in what your teach wants than in what you're given to work with.
  6. Oct 20, 2008 #5
    Could take the log of the inside to get the i th term?

    2i-1 - 1 = k (some constant)

    Take lg of each side
    2i-1 = k +1
    i-1 = lg(k+1)

    i = lg(k+1) + 1
  7. Oct 20, 2008 #6


    Staff: Mentor

    No. You have to take the log of each side of an equation, not just parts of it.

    If you want me to answer any more questions, please answer the ones I have asked.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook