Question

Preview File Edit View Go Tools Window Help Homework_6.pdf (1 page) Homework_5.pdf pagal 2. An array of n distinct integers is to be searched using Sequential Search. The probability that the search key matches the last item in the array is y, and the probability that the item searched for is not present in the array is likewise y. The probabilities of matching the 19through (n-1)"items are all equal. What is the average case time complexity, A(n), where the basic operation is one comparison of an item with the search key?

Answer 1

    n * (1/4). [Last element is the key]
+
    n * (1/4) [ Key not present in the array, so we have to search through all elements]
+
    (1/2)*(n-1/2) [Equal probability of the element to be found in any place]

Therefore, answer is : $( n/2 ) + ((n-1)/4)$