Linear time complexity
Linear time complexity is an asymptotic running-time bound that grows at most proportionally to the input size, or combined input sizes, ignoring constant factors.
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.
- How it is used
- Describes how work grows with input size when an algorithm makes a linear pass, such as searching an array.
- 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 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.
Read how Algorithms Every Programmer Should Know explains linear time complexity →
Latency
Linear time is an algorithmic growth class in which required operations increase proportionally to input size.
- How it is used
- Uses linear time to assess work growth and identify opportunities to reduce latency.
- How deep it goes
- Explains worst-case search and average-case distinctions, then demonstrates memoization and benchmarking.
- Examples
- Uses array search and recursive Fibonacci with a memoization cache.
- What you can do after
- Evaluate algorithm growth and compare implementations using Criterion benchmarks.
Practices of the Python Pro
- How it is used
- Uses input-growth analysis to estimate task duration and locate opportunities for performance improvement.
- How deep it goes
- Explains O(n) through line analogies, loop examples, repeated passes, and contrasts with higher-order growth.
- Examples
- Uses name lists, repeated loops, duplicate detection, and favorite-color file processing.
- What you can do after
- Evaluate code for likely O(n) behavior and choose data representations suited to scaling work.
Read how Practices of the Python Pro explains linear time complexity →
Grokking Data Structures
Linear growth is growth proportional to input size.
- How it is used
- Measures how algorithm running time grows as input size increases.
- How deep it goes
- Defines asymptotic linear growth and works through linear search, but stops short of formal proofs.
- Examples
- Uses linear search, array inversion, and dynamic-array queue resizing to illustrate linear work or storage.
- What you can do after
- Evaluate algorithm performance by identifying work that scales with input size and separating time from extra space.
Read how Grokking Data Structures explains linear time complexity →
Grokking Algorithms, Second Edition
Linear time describes an algorithmic running time that grows proportionally with the size of the input.
- How it is used
- Measures how an algorithm’s operation count grows as its input becomes larger.
- How deep it goes
- Defines O(n) through search and grid examples, contrasts O(log n), and stops short of exact operation-count guarantees.
- Examples
- Uses one-by-one phone-list searching, drawing a grid box by box, and quicksort’s worst-case call stack.
- What you can do after
- Evaluate/understand whether an algorithm’s running time grows linearly with input size and compare it with logarithmic time.
Read how Grokking Algorithms, Second Edition explains linear time complexity →
Advanced Algorithms and Data Structures
Linear time is a running-time bound proportional to the number of vertices and edges or other input elements being processed.
- How it is used
- Compares algorithmic designs by relating work to goods, characters, keys, or cache entries processed.
- How deep it goes
- Explains linear behavior through concrete bounds and assumptions, but stops short of formal proofs.
- Examples
- Uses fractional knapsack, longest-prefix search, Bloom-filter insertion, and LFU list bubbling as concrete cases.
- What you can do after
- Evaluate running-time trade-offs by identifying the input measure and checking whether preprocessing or representation changes the bound.
Read how Advanced Algorithms and Data Structures explains linear time complexity →
Python Workout: 50 ten-minute exercises
An asymptotic time complexity that grows proportionally with the number of elements processed.
- How it is used
- Explains the cost of searching Python sequences and guides selection of readable membership tests.
- How deep it goes
- Defines O(n), illustrates proportional growth, and stops short of detailed complexity analysis or implementation internals.
- Examples
- Uses an office-search analogy, vowel detection, Pig Latin processing, and Python membership code.
- What you can do after
- Apply linear-time membership tests to Python sequences and recognize when their cost is acceptable.
Read how Python Workout: 50 ten-minute exercises explains linear time complexity →
Learn C++ by Example
Linear complexity is an algorithmic growth rate proportional to the number of input elements, commonly expressed as O(n).
- How it is used
- Frames vector searching as a practical example of work proportional to input size.
- How deep it goes
- Defines O(n) through a worst-case vector search and contrasts it with tree-based searching without deriving formal bounds.
- Examples
- Uses searching a vector containing n elements and compares it with searching ordered map nodes.
- What you can do after
- Evaluate how input growth affects search work and compare sequential searching with tree-based lookup.
Read how Learn C++ by Example explains linear time complexity →
Elixir in Action, Third Edition
Linear time complexity is asymptotic running time that grows proportionally with the size of the input.
- How it is used
- Guides collection choices by exposing the traversal cost of common list operations.
- How deep it goes
- Explains O(n) through singly linked-list traversal and names costly operations, without broader complexity analysis.
- Examples
- Uses length/1, Enum.at/2, list replacement, insertion, appending, and ++ as concrete O(n) examples.
- What you can do after
- Evaluate list operations and choose another collection when direct access is required.
Read how Elixir in Action, Third Edition explains linear time complexity →
Also covered in
- Clojure: The Essential Reference
- Build a DeepSeek Model (From Scratch)In early access (MEAP)
- Julia as a Second Language
- Object-Oriented Software Design in C++
- Fabulous Adventures in Data Structures and Algorithms
What to know first
- arrayAn array is an ordered collection of elements organized in one or more dimensions and accessible by position or index.
- loopA loop is a programming-language control-flow construct that repeatedly executes a block of instructions according to an iteration rule or continuation condition.
- linked listAn ordered sequence of elements stored in separate nodes connected by links or references rather than in one contiguous storage region.
- MapA map is an associative data structure that stores key-value associations and supports retrieving values by key.
Related concepts
- linear searchmeasures · Linear search is a search technique that examines candidates sequentially until it finds a match or exhausts the collection.
- time complexitykind of · Time complexity describes how an algorithm’s execution time grows as a function of its input size or parameters.
- performancekind of · Performance is a measure of how effectively a person, process, model, or system achieves its objectives, including qualities such as output quality, speed, and resource efficiency.
- logarithmic time complexitycontrasts with · An algorithmic running-time growth rate proportional to the logarithm of the input size, commonly expressed as O(log n).
- traversalmeasured by · Traversal is the systematic process of visiting elements or nodes in a data structure according to a specified order or rule.
- exact-match accuracymeasured by · Exact-match accuracy is the proportion of predictions or outputs that equal their reference answers under specified comparison rules.
Questions about linear time complexity
What is linear time complexity?
Linear time complexity is an asymptotic running-time bound that grows at most proportionally to the input size, or combined input sizes, ignoring constant factors.
Which Manning books explain linear time complexity?
Algorithms Every Programmer Should Know, Latency, Practices of the Python Pro, Grokking Data Structures, Grokking Algorithms, Second Edition, Advanced Algorithms and Data Structures, Python Workout: 50 ten-minute exercises, Learn C++ by Example and 1 more.
What should I know before learning linear time complexity?
Manning books that teach linear time complexity usually introduce array, loop, linked list and Map first.
What is the difference between linear time complexity and logarithmic time complexity?
Linear time complexity is an asymptotic running-time bound that grows at most proportionally to the input size, or combined input sizes, ignoring constant factors. An algorithmic running-time growth rate proportional to the logarithm of the input size, commonly expressed as O(log n).
What is linear time complexity a kind of?
Linear time complexity is a kind of time complexity. Time complexity describes how an algorithm’s execution time grows as a function of its input size or parameters.
What is linear time complexity also called?
Linear time complexity is also called O(n) or linear complexity.
These guides are generated from the text of Manning books by Manning's knowledge graph and link to the sections they draw on. The full books are available on liveBook and at manning.com.








