Reference no: EM131636750

Question: Our existing binary search algorithm (Chapter 3, Example 13) contains the pseudocode instruction find the index k midway between i and j after which the target x is compared to the list item at index k, the "midpoint item." Suppose that this instruction is replaced by

if i = j then

   k = j

else

   k = i + 1

end if

a. Draw the decision tree that results from using the modified algorithm on a sorted list with n = 8.

b. Give the exact number of comparisons required in the worst case for n = 8.

c. Give a worst-case order-of-magnitude expression for the number of comparisons required as a function of n, and justify your expression. Comment on the use of this algorithm as opposed to the original binary search algorithm, which is Θ(log n).