Why is linear search still O(n) even though it exits early on the first match?

## What linear search actually does A linear (sequential) search walks a collection from one end to the other, testing each element against a predicate or a target key, and stops the moment the test succeeds. It makes no assumptions about the data: no ordering, no index, no precomputation. That is its whole selling point — it is the only search that works on arbitrary unsorted input, and it is the baseline every cleverer search is measured against. ## The three cases - **Best case, O(1):** the target is the first element examined. One comparison, done. - **Average case, about n/2 comparisons:** if the target is present and equally likely to be at any position, the expected number of comparisons is `(n+1)/2`. - **Worst case, O(n):** the target is in the last position examined, or it is not there at all. Every element is tested. The complexity label attaches to the worst case, so the algorithm is O(n) — and, because there are inputs that genuinely require touching every element, it is also Θ(n) in the worst case rather than merely bounded by it. ## Why n/2 is not a better complexity class This is the misconception the question exists to kill. Asymptotic notation deliberately discards constant factors, because they depend on machine, data layout and comparison cost rather than on the algorithm's structure. `n/2` and `n` grow the same way: double the input, double the work. Halving the constant is a genuine engineering win — it is not a change of complexity class, and it never closes the gap with a logarithmic search as `n` grows. Writing "O(n/2)" is a category error; the notation has already thrown that factor away. There is a second, subtler point hiding in "average case". `n/2` is a claim about the **inputs**, not about the algorithm: it assumes the target is present and uniformly positioned. Change the distribution and the number changes with it. A workload where most lookups miss has an average of exactly `n` comparisons, because every miss is a full scan. A workload where the hot handful of records is kept at the front has an average close to 1. Neither is a property of linear search; both are properties of how the data is arranged and queried. (Note that average-case reasoning is also distinct from *amortized* reasoning: amortized bounds total cost over a worst-case *sequence* of operations and assume nothing about input distribution.) ## The asymmetry that matters in practice Early exit is a one-sided optimization. It can only shorten a **successful** search. An unsuccessful search — proving that nothing in the buffer matches — has no shortcut available: absence is only established by exhaustion. This is why the shape of your workload determines whether early exit is worth talking about at all. Consider a packet-capture triage tool scanning an unsorted buffer of roughly thirty captured records for the first one with a bad checksum. If corruption is common, early exit fires quickly and the average scan is short. But the interesting operational case is the clean buffer, where the tool must inspect all thirty records to report "no malformed packets" — and that is the case that runs on every healthy capture, which is most of them. A validation pass that usually succeeds pays the worst case almost every time. So the honest description is not "it's fast because it exits early"; it is "successful lookups are often short, and every clean pass costs a full scan". ## The direction of the claim Two directions are easy to get backwards, and interviewers listen for both. First, O(n) is an **upper bound on growth**, not a prediction of runtime. Labelling something O(n) does not say it is slow; on a compact buffer of a few dozen fixed-size records, a linear scan is a tight, branch-predictable loop over contiguous memory and can be faster in wall-clock terms than a structure with a better bound. Second, early exit changes *which* case you land in, never *what the cases are*. If someone claims early exit makes the search sublinear, ask them what happens when the element is missing. The answer — every element, every time — is the whole bound. ## What to say in an interview Name the three cases, state that the bound comes from the worst one, point out that `n/2` is a constant factor rather than a class, and then volunteer the asymmetry: successful searches can be short, unsuccessful ones cannot. That last sentence is what separates a memorised answer from an understood one.