Asked by waqaszahid
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?
(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?
Answers
There are no human answers yet.
There are no AI answers yet. The ability to request AI answers is coming soon!
Submit Your Answer
We prioritize human answers over AI answers.
If you are human, and you can answer this question, please submit your answer.