Looking for a number in an unsorted array? Linear search checks elements one by one until it finds the target or reaches the end. If the array has N elements, the search may make N checks. Its time complexity is O(N): as the input grows, the work grows with it. section 1.3.1
The letter names the input size, not a particular number of seconds. When the input is a pattern of length m, the same linear bound is written O(m). Building the lookup array for Knuth–Morris–Pratt (KMP) pattern matching is one example. section 1.3.1 section 5.1.1
A linear pass over a pattern
For the pattern “aabadc,” KMP builds the LPS lookup array [0, 1, 0, 1, 0, 0]. It tracks prefix–suffix matches while working through the pattern; construction takes O(m) time for a pattern of length m. section 5.1.1
Keep the input and the resource being measured clear:
- O(N) time describes growing work, as in linear search. O(N) space describes growing storage, as in a stack holding N elements; its push and pop operations are O(1) time. section 1.3.1 section 1.4.3
- With two input lengths, a bound can name both: Rabin–Karp’s average time is O(n+m) for text length n and pattern length m, while its worst case is O(n×m). section 4.4
- A hash map’s insert, search, and delete operations are described as near O(1) with a well-designed hash function, but can reach O(N) in the worst case with a poor one. section 1.4.1
Figure 1.2 A graph showing the time complexities with varying inputs. O(1) is the constant time, while O(n!) shows the worst time. O(log n) is logarithmic, and O(n) is linear time. Quadratic and cubic are in between and work well for smaller values of n.
Compare the O(N) line with constant, logarithmic, and faster-growing complexity curves as input size increases. section 1.3.1








