Expected Value

Probability theory and statistics

Expected Value

Postby Guest » Sun Sep 19, 2021 11:47 am

Consider the sequential search algorithm for an unordered list of n elements and a target value x. Find the expected value X of the number of comparisons to search for x if x is equally likely to be at any of the n positions in the list or not in the list.
Guest
 

Re: Expected Value

Postby Guest » Sun Nov 07, 2021 10:14 pm

Since the target value is equally likely to be any of the n numbers, the probability it is a specific number is 1/n. With a sequential search, the expected value of X is [tex]\sum_{i=1}^n i/n= (1/n)\sum_{i=1}^n i= (1/n)(n(n+1)/2)= (n+1)/2. You would "expect" to find the middle number.
Guest
 

Re: Expected Value

Postby Guest » Sun Nov 07, 2021 10:19 pm

Since the target value is equally likely to be any of the n numbers, the probability it is a specific number is 1/n. With a sequential search, the expected value of X is [tex]\sum_{i=1}^n i/n= (1/n)\sum_{i=1}^n i= (1/n)(n(n+1)/2)= (n+1)/2[/tex]. You would "expect" to find the middle number.
Guest
 


Return to Probabilities and Statistics



Who is online

Users browsing this forum: No registered users and 3 guests