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 binary from $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 modified program be compared to the original version of binary?

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?

enter image description here

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?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.