- #1
Gear2d
- 51
- 0
Homework Statement
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)
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?