Linear Search Calculator
Solve the linear search relation ⟨C⟩ = (n + 1) / 2 for any of its quantities — array size, average comparisons, or worst-case comparisons — with step-by-step math, a live array scan, and O(n) complexity breakdown.
Every element costs one comparison
Linear search checks the array one element at a time, from start to end. Each check is one comparison. If the target is at position i (counting from 1), the search takes exactly i comparisons. That is why the average is the mean of positions 1 through n: (1 + 2 + … + n) / n = (n + 1) / 2.
Roughly half the array on average
For a uniformly random target, on average you will inspect about half the elements before finding it. Doubling the array size doubles the expected number of comparisons. This is what O(n) means: the cost grows in direct proportion to the amount of data. Linear search is the reference against which every faster search is measured.
Worst case = unsuccessful search
When the target is not in the array, linear search must inspect all n elements before concluding it is absent. So the worst case for a successful search (target at the last position) and the cost of a failed search are both exactly n. This is why linear search is a poor choice when misses are common — the full scan cost is paid every time.
No precondition, no setup, no memory
Linear search is the only search that requires nothing of its input: no sorting, no hashing, no indexing, no auxiliary structure. It runs in place with O(1) extra space and works on any iterable, including streams and linked lists. Its simplicity makes it the fastest choice for very small arrays (n ≤ ~20) where the overhead of building an index would dominate the search itself.
How to Use This Calculator
The linear search relation links three quantities: array size, average comparisons, and worst-case comparisons. Edit any one and the other two update automatically.
1. Edit any field
Type a new value or drag the slider for n, ⟨C⟩, or C_max. The calculator keeps the other two in sync using the relations n = 2·⟨C⟩ − 1 and C_max = n.
2. Use realistic presets
Presets cover the usual dataset sizes — from 10 elements up to a billion. Average and worst-case presets are matched to those n values so the numbers line up.
3. Pick which value to feature
The three toggle buttons at the top ("Show as result") control which value appears big on the result card. All three fields stay editable regardless.
4. Follow the array scan
The diagram shows the linear scan: elements are checked in order from left to right, and the target is highlighted at its position. Watch the checked-element counter increase.
5. Check the charts
The first chart plots comparisons against array size for best, average, worst, and total-cost curves. Advanced mode adds a bar chart showing comparisons needed at each position.
6. Switch to Advanced for depth
Advanced mode adds the per-position bar chart, a sensitivity check on a +1% input change, and companion metrics including the comparison against binary search.
What This Tool Offers
Built around the linear search relation ⟨C⟩ = (n + 1) / 2 — the fundamental measure of how many comparisons an unindexed scan costs on average.
Three-way sync
Edit any of n, ⟨C⟩, or C_max and the other two update automatically. No modes, no locking — the calculator stays consistent.
Live array scan
A visual of the linear scan, with elements highlighted as they are checked and the target position clearly marked.
Size-class verdict
Each result is classified from trivial (a handful of elements) through tiny, small, medium, large, and huge dataset classes.
Comparison charts
Best, average, worst, and total-cost curves on the same axes, plus an advanced per-position bar chart showing the cost at each index.
Half-integer precision
Average comparisons for even n are half-integers like 5.5 or 500.5 — the calculator preserves them exactly rather than rounding them away.
Reference tables
Comparison counts by array size, a search algorithm complexity matrix, and a full variable reference.
Reference Tables & Conversions
A linked array-size ↔ comparisons converter, comparison counts by size, and a search algorithm complexity matrix.
Array size ↔ comparisons converter
Comparison Counts by Array Size
Linear search cost alongside binary search for direct comparison — showing why the O(log n) advantage becomes dramatic past a few hundred elements.
| n | Linear best | Linear avg (n+1)/2 | Linear worst (n) | Binary worst ⌊log₂ n⌋+1 | Binary speedup |
|---|
Search Algorithm Complexity Reference
| Algorithm | Best | Average | Worst | Requires sorted | Space |
|---|---|---|---|---|---|
| Linear search | O(1) | O(n) | O(n) | No | O(1) |
| Binary search | O(1) | O(log n) | O(log n) | Yes | O(1) |
| Jump search | O(1) | O(√n) | O(√n) | Yes | O(1) |
| Interpolation search | O(1) | O(log log n) | O(n) | Yes | O(1) |
| Exponential search | O(1) | O(log n) | O(log n) | Yes | O(1) |
| Hash table lookup | O(1) | O(1) | O(n) | No | O(n) |
| Balanced BST | O(log n) | O(log n) | O(log n) | Maintained | O(n) |
Variable Reference
| Symbol | Meaning | Typical range | Formula |
|---|---|---|---|
| n | Array size (number of elements) | 1 – 10¹² | input |
| i | Position of the target (1-indexed) | 1 – n | input |
| Cbest | Best-case comparisons | 1 | 1 (target at position 1) |
| ⟨C⟩ | Average-case comparisons (successful) | 1 – 5×10¹¹ | (n + 1) / 2 |
| Cmax | Worst-case comparisons (or unsuccessful) | 1 – 10¹² | n |
| ΣC | Total cost across all n positions | 1 – 5×10²³ | n(n + 1) / 2 |
| P(i) | Probability of finding at position i | 1/n | 1 / n (uniform) |
What Does ⟨C⟩ = (n + 1) / 2 Measure?
The relation gives the expected number of comparisons linear search performs when the target is equally likely to be in any of the n array positions. It is the simplest possible formula in algorithm analysis — and its simplicity is the whole point. Linear search is the baseline against which every faster algorithm is compared, and (n + 1) / 2 is the number you get when the data has no structure you can exploit.
The Linear Search Formula
Linear search scans the array from left to right, comparing each element to the target. If the target is at position i (counting from 1), the search costs exactly i comparisons. Assuming every position is equally likely, the expected cost is the mean of 1 through n:
Rearranged to solve for the other quantities:
Cmax = n (worst case = unsuccessful search)
ΣC = n(n + 1) / 2 (total cost across all positions)
The best case is trivially 1 comparison — when the target happens to be the very first element. The worst case is n comparisons — when the target is the last element, or absent from the array entirely.
Linear Search Variables
| Symbol | Meaning | Notes |
|---|---|---|
| n | Array size | No precondition — works on any array |
| i | Position of the target | 1-indexed; cost equals i comparisons |
| Cbest | Best-case comparisons | 1 — target is at position 1 |
| ⟨C⟩ | Average-case comparisons | (n + 1) / 2 — half the array on average |
| Cmax | Worst-case comparisons | n — target is last or missing |
| ΣC | Total cost across all positions | n(n + 1) / 2 — sum 1 through n |
How Array Size Affects Linear Search
The relation is linear in n, which is the whole story of linear search's performance. Doubling the array doubles both the average and worst case. A hundredfold increase in data gives a hundredfold increase in expected comparisons. There is no clever trick, no logarithm, no sub-linear behaviour — the algorithm simply has to look at every element it needs to look at, and on average that is half the array.
This is why indexing exists. Every faster search algorithm — binary search, hashing, B-trees, inverted indexes — works by pre-processing the data so that the search can skip over most of it. Binary search achieves O(log n) by requiring the array to be sorted; hashing achieves O(1) average by requiring an auxiliary table. Both pay a setup cost, and both beat linear search decisively once n grows past a few hundred. For n below about 20, though, the setup cost of an index exceeds the search cost, and linear search wins on simplicity.
The other important observation is that linear search's worst case equals its unsuccessful-search cost. When the target is not present, every element must be inspected before the algorithm can conclude the element is absent. This is why linear search is a poor fit for negative lookups — the full n-comparison cost is paid on every miss, every time. If misses are common in your workload, an index is not optional.
Linear Search Calculation Examples
⟨C⟩ = (1,000 + 1) / 2 = 500.5 comparisons
n = 2 × 50.5 − 1 = 100 elements
ΣC = 1,000,000 × 1,000,001 / 2 = 500,000,500,000 comparisons
Linear avg = 500,000.5 · Binary worst = 20
Binary is 25,000× fewer comparisons
Frequently Asked Questions
Because positions are 1-indexed. If you find the target at position i, you have made exactly i comparisons. Averaging over i = 1 to n gives (1 + 2 + … + n) / n = (n + 1) / 2. If you used 0-indexed positions and counted comparisons as i + 1, you would get the same formula. The extra 1/2 above n/2 is a small but real consequence of 1-indexing: the average position is (n + 1) / 2, not n / 2. For large n the difference is negligible, but the exact formula keeps the half-integer precision.
Correct — linear search is the only common search algorithm that works on completely unsorted data. It simply iterates through the array and checks each element. This is its biggest advantage: you can use it on a stream, a linked list, a temporary buffer, or anything that has not been prepared for faster lookup. The trade-off is O(n) time: you pay for the lack of preprocessing with the lack of algorithmic speedup.
Three cases. First, tiny arrays — below 20–30 elements the overhead of setting up an index exceeds the benefit, and linear search's tight loop with sequential memory access is faster than more complex alternatives. Second, one-off searches on unsorted data — if you will only search once, sorting the array is wasted work. Third, streaming or non-indexable data — when the input is a linked list, a network stream, or a generator with no random access, linear search is the only option. In all three cases the O(n) cost is either small or unavoidable.
Finding the minimum or maximum of an unsorted array always requires n − 1 comparisons, because you must look at every element to be sure you have not missed a smaller or larger one. This is exactly the worst case of linear search and it is provably optimal — no algorithm can do better on unsorted data. The average case (n + 1) / 2 applies only when the target is at a uniformly random position; min/max is a different problem where you always pay the full scan cost.
In a typical implementation you compare each element against the target once. With n elements, you make n comparisons and then conclude the target is absent. If your loop is written as for (i = 0; i < n; i++) if (arr[i] == target) return i;, you make exactly n comparisons. Some formulations with a sentinel element at the end append the target and make n + 1 comparisons, but that is an implementation detail — the fundamental unsuccessful cost is n. Our calculator uses the standard n.
Binary search is asymptotically superior — O(log n) vs O(n) — but it requires the array to be sorted, which costs O(n log n) to set up. For a single search, linear search is almost always faster because sorting the array costs more than the scan. For repeated searches on the same data, binary search wins dramatically: 20 comparisons instead of 500,000 on a million-element array. The crossover is roughly 10–20 searches on the same data, after which the sorting cost is amortised. Also, binary search needs random access, so it does not work on linked lists or streams, whereas linear search does.
Variables
| Symbol | Quantity | Unit |
|---|---|---|
| Avg Comparisons | Average number of comparisons | |
| n | Number of elements |
What it means
Linear search is the simplest search algorithm: it scans each element in a list until it finds the target or reaches the end. Its time complexity is O(n). For a uniform distribution of the target position, the average number of comparisons (assuming the target is present) is (1 + 2 + ... + n)/n = (n+1)/2. If the target may be absent, the average includes an extra check of all n elements, giving an average of n comparisons in the unsuccessful case. In practice, linear search is used for small lists or unsorted data where binary search is not applicable. Although inefficient for large datasets, its simplicity and O(1) space make it useful in certain contexts, such as searching in linked lists or when the overhead of sorting is unjustified. Understanding the average and worst‑case behavior helps in choosing the right search algorithm based on the data size and access patterns. The formula (n+1)/2 is a classic example of expected value computation in algorithm analysis.
Worked example
Linear Search Average Comparisons – Two Examples
Real‑World| Parameter | Value |
|---|---|
| n | 1000 |
| Average comparisons | (1000+1)/2 = 500.5 |
| Parameter | Value |
|---|---|
| n | 10,000 |
| Average comparisons | 10,001/2 = 5,000.5 |
Common mistakes
- Average vs. worst: (n+1)/2 is the average number of comparisons for a successful search (assuming equally likely keys). Worst‑case is n.
- Target not present: If the target is not in the array, linear search always makes n comparisons.
- Fractional comparisons: The average can be non‑integer; use (n+1)/2 as a real number.
- Sorted data irrelevant: Linear search does not require sorted data; binary search is faster but needs sorted input.
- Early termination: The average formula assumes the search stops when the target is found; if not found, it’s n comparisons.
Applications
Linear search (or sequential search) scans each element one by one until the target is found or the end is reached. Its average number of comparisons for a random target is (n+1)/2, making it O(n) on average. Despite its simplicity and O(n) efficiency, it is often the best choice for small, unsorted, or frequently changing datasets where the overhead of sorting is unjustified. It is used in searching linked lists, small arrays, and in situations where data is accessed sequentially (e.g., streaming). In practice, linear search is also a building block for more complex algorithms like string matching and pattern searching. Understanding its average‑case behaviour helps engineers decide when a more sophisticated search is necessary and when simple sequential scanning is sufficient.
- Searching in unsorted or small arrays
- Linked list searching
- Sequential data streams and file scanning
- Basic building block for pattern matching
- Educational introduction to searching algorithms
Related calculators · Algorithms
Recently updated formulas
Suggest an improvement
Found a mistake? Have a better example? Let us know.
You may send up to 3 suggestions per 24 hours.