Question

Lower bound arguments. In class, we proved that any comparison-based algorithm that has to sort n numbers runs in Ω (nlogn) time. Let’s change the problem a bit. Suppose S[1. . . n] is a sorted array. We want to know if S contains some element x.
a. How would you solve this problem and what is the running time of your algorithm? (Note: you can just say what algorithm you will use.)
b. Show that any comparison-based algorithm(i.e., one that asks “Is S[i] ≤ z”?) that solves this problem runs in Ω (logn)time. Use a similar argument we made in class.

Answer 1

For part(a) it stands very simple as if the array is sorted and we repeated divide the array into half and search by comparison for the given element, we will either move in the left or right half. Because at the middle element any element will either be greater or smaller to it (as the array is sorted). Hence on each repetitive iteration, we need to deal with the remaining half of the array and hence, the running time will be or order O(logn).

For part (b) as the type of argument made in class is not given, any assertion can not be given. Though the above explanation must be sufficient to help you further.