Binary Search Comparison Recurrence Relation: Solve and Prove Solution"

[Gear2d]

Homework Statement

Solve and prove your solution for the following recurrence relation for the number of comparisons in Binary Search:

C(2¹ - 1)=1
C(2ⁱ - 1) = 2 + C(2⁽ⁱ⁺¹⁾ - 1)

The Attempt at a Solution

The setup for this would be:

C(n)={ 1, n=1 and 2 + C(2⁽ⁱ⁺¹⁾ - 1), otherwise

From this I would do substitution and guessing, and then prove the guess with induction?

 

[Mark44]

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.

 

[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

 

[Mark44]

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

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

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.

 

[Gear2d]

Could take the log of the inside to get the i th term?

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

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

i = lg(k+1) + 1

 

[Mark44]

Could take the log of the inside to get the i th term?

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

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

i = lg(k+1) + 1

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.