liveBook · Manning

Linear time complexity

Also called O(n), linear 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.

How 9 Manning books explain it

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.

Read how Latency explains linear time complexity →

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

What to know first

Related concepts

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.