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:
“A commodity appears at first sight an extremely obvious, trivial thing. But its analysis brings out that it is a very strange thing, abounding in metaphysical subtleties and theological niceties.”
—Karl Marx (1818–1883)
“The spider-mind acquires a faculty of memory, and, with it, a singular skill of analysis and synthesis, taking apart and putting together in different relations the meshes of its trap. Man had in the beginning no power of analysis or synthesis approaching that of the spider, or even of the honey-bee; but he had acute sensibility to the higher forces.”
—Henry Brooks Adams (1838–1918)