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, for n = 2 this is 1, corresponding to a single if-then-else construct).