Editing Linear search (section)

==Analysis==
For a list with ''n'' items, the best case is when the value is equal to the first element of the list, in which case only one comparison is needed. 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

:<math>
\begin{cases} 
  n                   & \mbox{if } k = 0 \\[5pt]
  \displaystyle\frac{n + 1}{k + 1} & \mbox{if } 1 \le k \le n.
\end{cases}
</math>

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 <math>\frac{n + 1}2</math>. However, if it is ''known'' that it occurs once, then at most ''n'' - 1 comparisons are needed, and the expected number of comparisons is 
:<math>\displaystyle\frac{(n + 2)(n-1)}{2n}</math>

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

Either way, [[asymptotic complexity|asymptotically]] the worst-case cost and the expected cost of linear search are both [[big O notation|O]](''n'').

===Non-uniform probabilities===
The performance of linear search improves if the desired value is more likely to be near the beginning of the list than to its end.  Therefore, if some values are much more likely to be searched than others,  it is desirable to place them at the beginning of the list.

In particular, when the list items are arranged in order of decreasing probability, and these probabilities are [[geometric distribution|geometrically distributed]], the cost of linear search is only O(1). <ref name="knuth">
  {{cite book
  | first=Donald |last=Knuth |author-link=Donald Knuth
  | series = The Art of Computer Programming
  | volume = 3 |title=Sorting and Searching
  | edition = 3rd
  | publisher = Addison-Wesley
  | year = 1997
  | isbn = 0-201-89685-0
  | chapter = Section 6.1: Sequential Searching
  | pages = 396–408
  }}
</ref>