Linear search
Walk the list from one end, comparing each element with the target, and stop when it is found or when the list runs out. The target here is deliberately absent, so the walk always runs to the end and the count is exactly n. That makes this the worst case rather than an average, which is the honest thing to measure: an average depends on where the target usually is, and nothing about the algorithm decides that.
The claim being tested
O(n)
When it is the right choice
When the data is not sorted and will not be searched often, when it is small enough that the constant factors dominate any asymptotic argument, or when there is no ordering to exploit at all. It is also the thing to reach for when the alternative is sorting first: one linear search is cheaper than a sort, and it is a common mistake to reach for the clever structure before counting how many searches there will actually be.
How it works
- Start at the first element.
- Compare it with the target and count the read.
- If it matches, stop; otherwise move to the next.
- Stop at the end of the list. The count is the number of reads.
Worth noticing
- On log-log axes this is a straight line at gradient exactly 1, and that is the reading this whole tool turns on: the gradient is the exponent, and the exponent of n is one. Every other curve here is read as steeper or flatter than this one.
- Doubling n doubles the count, every single time, with no drift at all. The fit is exact because the count is exactly n rather than approximately n.
- The shape of the input makes no difference whatever, and the measurement shows it: shuffled, sorted and reversed all give the same count. That is worth having on the same page as insertion sort, where the shape decides the complexity class.
Cost
- Best
- O(1)
- Average
- O(n)
- Worst
- O(n)
- Extra space
- O(1)
- n is
- the length of a list of numbers
- Measures
- shuffled: up to n = 131,072; sorted: up to n = 131,072; reversed: up to n = 131,072
The ceilings are a time limit rather than a memory one, which makes this tool the odd one out in the suite. Its recorded steps are tiny — one step per measured size, not one per operation — so nothing about the trace would ever stop a run. What has to be stopped is the measuring itself: a configuration that would take more than forty million operations to count is refused before a single one of them is counted, from a formula in the input sizes rather than by starting and giving up. Two further limits sit beside it that no formula in operations can see: building the input is real work, and a recursion n deep overflows the call stack long before its operation count becomes interesting.
A fit over a dozen sizes is evidence and not proof. It cannot rule out a term that only begins to matter past the largest size measured, and it says nothing at all about the constant factors that decide which of two algorithms in the same class is actually faster on a real machine.