liveBook · Manning

Linear time complexity

As explained in Algorithms Every Programmer Should Know

An asymptotic linear-time bound in an input of size N, also written O(m) when that input's size is denoted m.

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

How Algorithms Every Programmer Should Know covers it

How deep it goes
Explains O(N) through array iteration and illustrates O(m) through a worked pattern lookup-array construction.
Examples
Uses an array search and the pattern “aabadc” with its LPS array to illustrate linear work.
What it assumes
Assumes familiarity with arrays and loops while introducing time-complexity categories through linear search.
What you can do after
Evaluate/understand whether a stated O(N) or O(m) bound measures time or space and which input size it uses.
How it connects
Connects linear time to linear search, time and space complexity, hash maps, and string-matching algorithms.

Also explained in

Compare how 9 books explain linear time complexity →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Algorithms Every Programmer Should Know. The section links point to the parts of the book it draws on.