Linear search examines elements sequentially until the target is found or the collection is exhausted. Its worst-case comparison count is n, while its average successful-search comparison count is (n + 1)/2 when every position is equally likely to contain the target.
Linear Search Comparison Count
Linear search examines elements sequentially until the target is found or the collection is exhausted. Its worst-case comparison count is n, while its average successful-search comparison count is (n + 1)/2 when every position is equally likely to contain the target.
\(C_{\mathrm{max}}(n) = n; C_{\mathrm{avg}}(n) = (n + 1)/2\)
What this formula means
Scientific principle
Principle
Unlike binary search, linear search does not eliminate a large portion of the remaining collection after each comparison. It checks elements one at a time, so the number of comparisons grows proportionally to the input size.
Derivation
1. Let n be the number of elements.
2. In the worst case, the target is the last element or is absent.
3. Therefore, all n elements may need to be examined, giving C_max(n) = n.
4. For a successful search, assume the target is equally likely to occur at any position from 1 to n.
5. The possible comparison counts are 1, 2, 3, ..., n.
6. Their average is (1 + 2 + ... + n)/n.
7. Using the arithmetic-series sum n(n + 1)/2 gives C_avg(n) = (n + 1)/2.
Final Result
C_max(n) = n; C_avg(n) = (n + 1)/2
Best Case
C_best(n) = 1
Worst Case Complexity
T(n) = Θ(n)
Average Case Complexity
T_avg(n) = Θ(n)
Variables and their meanings
| Symbol | Meaning | Unit |
|---|---|---|
n | Number of elements in the collection | Elements |
C_max(n) | Worst-case comparison count | Comparison operations |
C_avg(n) | Average successful-search comparison count | Comparison operations |
C_best(n) | Best-case comparison count | Comparison operations |
SI units and conversions
Comparison Count
Dimensionless operation count
Input Size
Number of elements
Complexity Class
Θ(n)
Conditions of use
The algorithm examines elements sequentially.
Each equality comparison is assumed to have constant cost.
The average successful-search formula assumes every position is equally likely to contain the target.
The worst-case formula applies when the target is last or absent.
Limitations and assumptions
The average comparison count changes if target positions have unequal probabilities.
For an unsuccessful search, all n elements must be examined.
The formula counts comparisons and does not include memory-access or input-loading costs.
Linear search does not require the input to be sorted.
For an empty collection, the comparison count is zero rather than one.
Step-by-step worked examples
| Problem | Solution | Answer |
|---|---|---|
Calculate the worst-case and average successful-search comparison counts for a collection containing 20 elements. |
| Worst case: 20 comparisons. Average successful search: 10.5 comparisons. |
A linear search is performed on a collection of 50 elements. Determine the comparison count if the target is in position 7 and calculate the average successful-search count. |
| The specified search requires 7 comparisons, while the average successful-search count is 25.5. |
Real-world applications
Searching small unsorted arrays
Sequential record inspection
Simple list-processing algorithms
Searching linked lists
Finding an element in a short collection
Formula Meaning
Linear search examines elements sequentially until the target is found or the collection is exhausted. Its worst-case comparison count is n, while its average successful-search comparison count is (n + 1)/2 when every position is equally likely to contain the target.
Sources and further reading
No source has been supplied for this item yet. Treat the claim as needing editorial verification.