Question

Consider the "typical-case" performace for the search algorithsms. In orther words the average number of comparisons needed over all possible positions where the elements can be found.

a) used to locate and element in a list of n terms with linear search

b) used to locate an element in a list of n= n^k terms using binary search.

Answer 1

a. used to locate and element in a list of n terms with linear search: Linear search is a simple technique which searches the array elements from the first element in the list till the last element in the list. So, in the worst case, the maximum number of comparisons will happen when you search for an element which is in the last index of the array. In that case the worst number of comparisons required in Linear Search is O(n). The same happens with the average case as well. In numbers the avearge number of comparisons required is: n/2 that also belongs to O(n).

b. used to locate an element in a list of n= n^k terms using binary search: Binary search is a technique which every time divides the array into two halves using the formulat mid = (low + high) / 2; where low is the start of the array index and high is the last array index. And the mid element is compared with the key. If the element is found, it returns true, and if the element is less than the mid element, you should search only in the left half of the array, otherwise, should search in the right half of the array. Therefore, for each comparison, the array is divided into 2 halves. Suppose if n is 2^k, then the number of elements to be compared in each pass is: 2^(k-1), 2^(k-2), .... so on. So, the required number of comparisons is k, i.e., log n. Therefore, in the worst case, the maximum number of comparisons required is: O(log n).