Recurrence Relation Help

  • Thread starter Gear2d
  • Start date
  • #1
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?
 

Answers and Replies

  • #2
34,527
6,219
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
51
0
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
34,527
6,219
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.
 
  • #5
51
0
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
34,527
6,219
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
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.
 

Related Threads on Recurrence Relation Help

Replies
4
Views
7K
Replies
3
Views
2K
  • Last Post
Replies
4
Views
1K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
0
Views
3K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
5
Views
1K
  • Last Post
Replies
2
Views
3K
Top