 The worst case is when the value is not in the list (or occurs only once at the end of the list), in which case "n" comparisons are needed.If the value being sought occurs "k" times in the list, and all orderings of the list are equally likely, the expected number of comparisons is

For example, if the value being sought occurs once in the list, and all orderings of the list are equally likely, the expected number of comparisons is formula_2.However, if it is "known" that it occurs once, then at most "n" - 1 comparisons are needed, and the expected number of comparisons is 

(for example, for "n" = 2 this is 1, corresponding to a single if-then-else construct).