Consider linear search again (see Exercise 2.1-4). How many elements of the input array need to be checked on average, assuming that the element being searched for is equally likely to be any element in the array? How about in the worst case? Using -notation, give the average-case and worst-case running times of linear search. Justify your answers.
Linear search is an algorithm as all the elements in the array have to be visited in the case when the required element is the last element in the array. This can also be categorized as the worst case scenario.
Worst case : The element is at the end of the array, hence, elements have to be visited.
Average case : We could assume the element to be found at the middle or the beginning of the array, this is wild. On average, the element can be found anywhere from the first to the element, ignoring the low order terms and removing the constants, we will end up with the element likely being at the nth element, hence on average, it is :
but
Ignoring constants and lower terms, we are left with
Â
Â