Assume that the given list has been sorted in ascending orde

Assume that the given list has been sorted in ascending order. Devise a recursive (Divide and Conquer) \"midterm\" search algorithm which first test the element at position n/5 for equality with some value x, and then possibly checks the element at position 4n/5. The result is either discovering x or reducing the set size to a fraction of the original. Give the recurrence relations of \"midterm\" search algorithm.

Solution

!) MIDTERM ALGORITHM PSEUDOCODE:

2) The Recurrence Relation of mid term search algorithm is:

T(N) = T(N/5) + O(1).

Time Complexity T(N) = log₅N