Linear time complexity
Linear time complexity is an asymptotic running-time growth rate proportional to input size, or to the combined sizes of multiple inputs, up to a constant factor.
Latency
Linear time is an algorithmic growth class in which required operations increase proportionally to input size.
- How it is used
- Guides work elimination in latency-sensitive code when input size or call frequency makes proportional growth consequential.
- How deep it goes
- Explains worst-case growth through array search and applies linear time to memoized Fibonacci without a formal complexity proof.
- Examples
- Uses an array search and measured recursive, memoized, and iterative Fibonacci implementations.
- What you can do after
- Apply it via Criterion and cargo bench to compare implementations and check whether eliminating repeated work reduces measured runtime.
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 →
Related concepts
- linear searchmeasures · Linear search is a search technique that examines candidates sequentially until it finds a match or exhausts the collection.
- performancekind of · Performance is the measurable effectiveness or operational behavior of a system under specified conditions, assessed through relevant qualities such as task results, speed, responsiveness, throughput, or resource use.
- logarithmic time complexitycontrasts with · An algorithmic running-time growth rate proportional to the logarithm of the input size, commonly expressed as O(log n).
- listmeasured by · list is a PersistenceLayer method that retrieves bookmark records in a specified ordering.
- traversalmeasured by · Traversal is the systematic process of visiting elements or nodes in a data structure according to its links, ordering, or a specified rule.
- exact-match accuracymeasured by · Exact-match accuracy evaluates outputs by whether they exactly equal their references under specified comparison rules.
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.