✦ScienexySCIENCE KNOWLEDGE LIBRARY
General science · SCI-FORM-COM-2066

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

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.

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

SymbolMeaningUnit

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

ProblemSolutionAnswer

Calculate the worst-case and average successful-search comparison counts for a collection containing 20 elements.

  • Given: n = 20.

  • Worst case: C_max = n = 20.

  • Average successful search: C_avg = (n + 1)/2.

  • C_avg = (20 + 1)/2.

  • C_avg = 21/2 = 10.5.

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.

  • Given: n = 50.

  • The target is at position 7.

  • A sequential search examines the first seven elements.

  • Actual comparisons = 7.

  • Average successful-search count = (50 + 1)/2 = 25.5.

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.

← Back to Formula Hub · Suggest a correction or source