Q3(b) Consider the following algorithm for searching for a given number x in an unsorted array A[1..n] having n distinct values. 1. Choose an i uniformly at random from 1..n 2. if A[i]=x then stop else goto 1 Assuming that x is present in A, what is expected number of comparisons made by algorithm before it terminates
Question
Q3(b) Consider the following algorithm for searching for a given number x in an unsorted array A[1..n] having n distinct values.
- Choose an i uniformly at random from 1..n
- if A[i]=x then stop else goto 1 Assuming that x is present in A, what is expected number of comparisons made by algorithm before it terminates
Solution
The given algorithm is essentially a random search algorithm. It randomly picks an index in the array and checks if the element at that index is the number we are looking for. If it is, the algorithm stops; if it isn't, the algorithm repeats the process.
The expected number of comparisons made by the algorithm before it terminates can be calculated using the concept of expected value in probability.
Since the array has n distinct values and x is guaranteed to be present in the array, the probability of finding x in any single attempt is 1/n.
The expected number of attempts (and thus comparisons) before finding x is the reciprocal of the probability of success on each attempt. This is a property of geometric distribution.
Therefore, the expected number of comparisons made by the algorithm before it terminates is n.
Similar Questions
n selection sort, after each pass through the array, what is guaranteed about the elements at the beginning of the array?a.They are sortedb.They remain unchangedc.They are in reverse orderd.They are randomly rearranged
What is the initial step in executing a binary search on a sorted array?*1 pointA. Traverse the entire array from start to end.B. Compare the target value to the middle element.C. Sort the array in ascending order.D. Calculate the average value of the elements.
In binary search, average number of comparison required for searching an element in a list if nnumbers is# (A) n log2 .(B) 2/n .(C) n.(D) n – 1.(E)n/2
The Average case occur in linear search algorithmQuestion 5Answera.When Item is the last element in the arrayb.When Item is the last element in the array or is not there at allc.When Item is not in the array at alld.When Item is somewhere in the middle of the array
Suppose there are 11 items in sorted order in an array. How many searches are required on average, if binary search is employed and all searches are successful in finding the item?
Upgrade your grade with Knowee
Get personalized homework help. Review tough concepts in more detail, or go deeper into your topic by exploring other relevant questions.