Linear time complexity describes work that grows in proportion to the number of input elements, commonly written as O(n). Searching a vector may require checking every element, including the final one or none at all. section 7.2.1
The comparison with map search highlights the practical cost of growth:
- A vector stores elements contiguously, so an unsuccessful search or a late match can inspect all n elements. section 7.2.1
- A map organizes key-value pairs in an ordered binary search tree, allowing a search to discard part of the tree at each step. section 7.2.1
Searching a vector
With n elements, checking items from the beginning until finding a match may require n comparisons. If no match exists, the search reaches the end and still performs work proportional to n. section 7.2.1
Figure 7.3 Constant time complexity: O(n) grows much faster than logarithmic complexity, O(log(n)), as the number of elements is increased.
Visualizes how O(n) grows faster than O(log(n)) as the number of elements increases. section 7.2.1
