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?
(b) If we change the dividing point computation in function binary from i = (l + r)/2 to i = r - 2, 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?

Similar Questions
  1. How can the momentum of a moving object be found?(1 point)Responses by dividing its velocity by the time it travels by dividing
    1. answers icon 1 answer
    1. answers icon 1 answer
  2. How does a firm calculate marginal cost?(1 point)Responses By dividing the change in total cost by the change in output. By
    1. answers icon 1 answer
  3. Which change to the table would make the relation a function?x 0 3 5 3 y 1 10 16 14 Responses Change (3, 14) to (4, 14). Pick
    1. answers icon 1 answer
more similar questions