0

For this following recurrence:

$$f(0) = 1,\\ f(1) = 1,\\ f(2) = 2,\\ f(2t) = f(t) + f(t + 1) + t\text{ (for }t > 1),\\ f(2t + 1) = f(t - 1) + f(t) + 1\text{ (for }t \ge 1).$$

After thorough research i know that this should be solved using a binary search one on the even indices and one for the odd.

However i have no idea on how to start with this. I do know what binary search is but have only used them to search for an element in an array.

Your help would be highly appreciated.

Also a code sample or pseudo code would be very helpful.

Regards, Omar

Edit:

To be more specific, I need a solution to be able to find the value t that produces the input x;

check this question for exactly what i need. the solution is there but did not really get it and would appreciate further elaboration.

convoluted recurrence: $f(2n)=f(n)+f(n+1)+n, f(2n+1)=f(n)+f(n-1)+1$

Omar El Cheikh
  • 17

1 Answers1

0

In the comment of the indicated answer there is a bounded interval in where to search recursively:

For n sufficiently large it should be the case that .39nlogn≤f(n)≤.5nlogn. This means if you are trying to solve f(n)=S then, for each S, there is only a finite range (depending on S) that needs to be searched. This gives an algorithm (once you prove the inequalities) for all n sufficiently large; smaller n can be searched through brute force.

Brethlosze
  • 3,010