Latest Lists

Element Comparisons in Unordered List?

I am given a sequential algorithm that does a routine search on an unordered list. N = 20. The probability that the value x does NOT appear in the list is exactly 60%, and the probability that x DOES appear is 40%. The 3 questions that I could not get were: A) What is the avg number of element comparisons performed when n = 20 and x does NOT appear in the List. (my answer was 20, is this correct?) B) What is the avg number of element comparisons performed when n = 20 and x DOES appear in the list? C) What is the avg number of element comparisons performed when n = 20. This should be a single number answer they said. Please explain answers.

Public Comments

1. A) yes, you are right. The algorithm will look at all 20 elements, none will be equal. So 20 comparisons. B) Well, sometimes you'll get lucky and the number will be in the first slot. You'll make 1 comparison, and be done. Other times it will be in the last slot, so you need to make 20 comparisons. (If you *really* know ahead of time that the item is in the list, you could do it in 19 compares and then proclaim it must be in slot 20. But no programmer in the real world writes code that way). The average is going to be: Min Comparisons + Max comparisons/2. Or 1 + 20 / 2 = 10.5. Or in the case where you know ahead of time: 1 + 19 / 2 = 10. I would be curious to know if your teacher would accept either answer as correct. 10 is probably the 'academic' answer. 10.5 is the real world answer. C) This is just a question of combining the answers from A and B, using the probabilities stated. So 60% of the time x won't be in the list, so we'll do 20 compares. 40% of the time x will appear, so we'll do 10.5 compares. So thats: .6 * 20 + .4 * 10.5 = 12 + 4.2 = 16.2 Or...Assuming they want B to be 10 not 10.5 .6 * 20 + .4 * 10 = 12 + 4 = 16