Recurrence Relation Help

1. Oct 19, 2008

Gear2d

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. Oct 19, 2008

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.

3. Oct 19, 2008

Gear2d

I am assuming that is what the teacher wants. Could this be it:

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

4. Oct 19, 2008

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.

5. Oct 20, 2008

Gear2d

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

6. Oct 20, 2008

Staff: Mentor

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