Consider the following algorithm for searching an item in an array. The algorithm takes an array, A, and an item, a, as inputs. It compares a with items in A sequentially. If a is in the array A, the algorithm returns the index of a (first index, if multiple a exist). If a is not in the array, the algorithm returns -1. For example, for inputs (A=['ab', 'cd', 'ef, 'gh', 'ij'), a='cd' ), it returns 2 (assuming the indexing of the array starts at 1).
SimpleSearch (A, a)
for i=1 to n
if A[i] == a
return i
return -1
What is the best-case runtime of this algorithm? Create an example of an input that will lead to the best-case run time.
