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
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 . 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).
Either way, asymptotically the worst-case cost and the expected cost of linear search are both O(n).
Read more about this topic: Linear Search
Famous quotes containing the word analysis:
“Ask anyone committed to Marxist analysis how many angels on the head of a pin, and you will be asked in return to never mind the angels, tell me who controls the production of pins.”
—Joan Didion (b. 1934)
“Analysis as an instrument of enlightenment and civilization is good, in so far as it shatters absurd convictions, acts as a solvent upon natural prejudices, and undermines authority; good, in other words, in that it sets free, refines, humanizes, makes slaves ripe for freedom. But it is bad, very bad, in so far as it stands in the way of action, cannot shape the vital forces, maims life at its roots. Analysis can be a very unappetizing affair, as much so as death.”
—Thomas Mann (1875–1955)