Array index
An array is a contiguous run of equally sized slots, so the address of the element at position k is the address of the first slot plus k times the slot size. That is one multiplication and one addition, and it does not depend on how many slots there are. The measurement here is therefore the same single read at every size, which is what O(1) means when it is stated precisely: not "fast", but "independent of n".
The claim being tested
O(1)
When it is the right choice
It is not a choice so much as the reason arrays exist, and it is the baseline every other structure is compared against. The point of measuring it is to have a flat line on the same axes as the others: a curve only means something next to a curve that does not move, and readers who have never seen constant time drawn tend to read every gentle slope as flat.
How it works
- Build a list of n numbers.
- Read the element halfway along it.
- Count that as one operation.
- Repeat at every size on the ladder, and notice that the count never changes.
Worth noticing
- The count is 1 at every size, so the fitted constant is exactly 1 and the deviation is exactly zero. That is the only subject here where the fit is perfect, and it is perfect because there is nothing to fit rather than because the measurement is especially good.
- On log-log axes a constant is a horizontal line, so its gradient is zero. That is worth seeing before reading the gradient of anything else: the gradient is the exponent, and the exponent of n⁰ is nought.
- This says nothing about whether the read is *fast*. A cache miss makes one array index slower than a hundred, and the operation count cannot see that. Counting operations measures growth, not time.
Cost
- Best
- O(1)
- Average
- O(1)
- Worst
- O(1)
- 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.