Space complexity
Space complexity measures how the memory or storage required by an algorithm grows as a function of input size.
Algorithms Every Programmer Should Know
A measure of how an algorithm's memory usage grows as a function of input size.
- How it is used
- Compares algorithms by how their memory needs grow with input, particularly when inputs are large or constraints are tight.
- How deep it goes
- Defines memory use, works through storage bounds for data structures and traversals, and explains table-size limits and a memory optimization.
- Examples
- Uses stacks, tree and graph traversals, a knapsack table, and shortest-path and flow algorithms to illustrate memory growth.
- What you can do after
- Evaluate/understand memory costs and choose between stored data structures, table sizes, and representations under input constraints.
Read how Algorithms Every Programmer Should Know explains space complexity →
Build AI Drug Discovery Pipelines
Memory complexity is an asymptotic measure of the memory required by an algorithm as input size grows.
- How it is used
- Guides clustering-method selection by exposing how molecular-library size and fingerprint dimensionality affect memory demands.
- How deep it goes
- Derives worst-case memory bounds for three clustering algorithms and contrasts materialized versus optimal Taylor-Butina implementations.
- Examples
- Uses pairwise distance matrices, centroids, molecular fingerprints, and RDKit clustering implementations as concrete memory examples.
- What you can do after
- Evaluate memory demands and identify when pairwise-distance materialization creates a quadratic scaling bottleneck.
Read how Build AI Drug Discovery Pipelines explains space complexity →
Graph Neural Networks in Action
Space complexity describes how the memory requirements of an algorithm grow as the size of its input increases.
- How it is used
- Guides GNN algorithm selection when graph size and computational resources constrain scalability.
- How deep it goes
- Defines Big O assessment and applies it to GNN memory trade-offs, but defers comprehensive notation and graph analysis.
- Examples
- Compares GCN’s full-graph storage with GraphSAGE’s sampled neighborhoods and mini-batches.
- What you can do after
- Evaluate GNN algorithms for memory scalability using Big O notation and published complexity analyses.
Read how Graph Neural Networks in Action explains space complexity →
Practices of the Python Pro
Space complexity is a measure of how an algorithm’s memory or storage requirement grows as its input size increases.
- How it is used
- Guides practical performance decisions by comparing memory and disk requirements as inputs grow.
- How deep it goes
- Explains qualitative growth, file-processing tradeoffs, automatic garbage collection, lists, and generators, without formal derivation.
- Examples
- Contrasts whole-file color counting with line-by-line processing and demonstrates generators through range and squared-number examples.
- What you can do after
- Apply it via Python file iteration and generators to reduce unnecessary memory consumption.
Read how Practices of the Python Pro explains space complexity →
Latency
Space complexity is the asymptotic growth of memory or storage required by an algorithm as input size increases.
- How it is used
- Frames memory and storage growth as the space dimension of algorithmic complexity.
- How deep it goes
- Defines asymptotic space growth and contrasts it with time complexity, but gives no detailed space calculations for specific algorithms.
- Examples
- Uses active e-commerce orders, array length, linear search, hash-table lookup, and big O growth curves.
- What you can do after
- Evaluate how an algorithm’s memory or storage requirements scale with input size using big O notation.
Also covered in
- Machine Learning Algorithms in Depth
- Grokking Algorithms, Second Edition
- Grokking Data Structures
- Timeless Algorithms, The Foundational IdeasIn early access (MEAP)
- Build a DeepSeek Model (From Scratch)In early access (MEAP)
What to know first
- loopA loop is a programming-language control-flow construct that repeatedly executes a block of instructions according to an iteration rule or continuation condition.
- graphA graph is a mathematical structure consisting of vertices and edges that connect pairs of vertices to represent relationships or connections.
- PythonPython is a high-level, general-purpose, dynamically typed programming language with readable syntax and support for multiple programming paradigms.
- MapA map is an associative data structure that stores key-value associations and supports retrieving values by key.
Related concepts
- performancemeasured by · 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.
- storage capacitymeasures · Storage capacity is the amount of persistent data a storage resource can hold or has available for use.
- quantizationaddressed by · Model quantization represents model parameters or computations with reduced-precision numerical values, often to lower storage or computational requirements.
- memorymeasures · Memory is a storage capability or mechanism for retaining information or computational state for later access or use.
- tabulationused by · Tabulation is a dynamic-programming implementation technique that computes and stores subproblem results in an explicit order, typically from smaller to larger subproblems.
- constant timecontrasts with · Constant time is an asymptotic running-time bound, conventionally denoted O(1), that remains bounded independently of input size.
Questions about space complexity
What is space complexity?
Space complexity measures how the memory or storage required by an algorithm grows as a function of input size.
Which Manning books explain space complexity?
Algorithms Every Programmer Should Know, Build AI Drug Discovery Pipelines, Graph Neural Networks in Action, Practices of the Python Pro and Latency.
What should I know before learning space complexity?
Manning books that teach space complexity usually introduce loop, graph, Python and Map first.
What is the difference between space complexity and constant time?
Space complexity measures how the memory or storage required by an algorithm grows as a function of input size. Constant time is an asymptotic running-time bound, conventionally denoted O(1), that remains bounded independently of input size.
What is space complexity also called?
Space complexity is also called memory complexity or memory requirement.
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.




