The problem is from Data Structures and Algorithm Analysis Edition 3.2 (Java Version) Book from Clifford A. Shaffer. It is from the third chapter exercises, problem number 3.13.20.
Below is how it is stated:
It is possible to change the way that we pick the dividing point in a binary search, and still get a working search routine. However, where we pick the dividing point could affect the performance of the algorithm.
(a) If we change the dividing point computation in function
binaryfrom $i = (l + r)/2$ to $i = (l + ((r −l)/3))$, what will the worst-case running time be in asymptotic terms? If the difference is only a constant time factor, how much slower or faster will the modiﬁed program be compared to the original version of
Here is my solution:
For the binary search algorithm, the dividing point is gained with $i = (l+r)/2$, where $i$ the dividing point, $l$ the lowest index of the sequence and $r$ the largest one. In my task the diving point is gained so, $i = l+((r - l)/3)$. Is the worst case in asymptotic terms right found?
So the following instance as an input, in the recursive expression, is the 2/3 of the remaining length of the sequence. Can this be correct and can I use n substituted with (3/2)^k in this case, and considering the floor value of it since it is natural number?