liveBook · Manning

Space complexity

Also called memory complexity, memory requirement

Space complexity measures how the memory or storage required by an algorithm grows as a function of input size.

How 5 Manning books explain it

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.

Read how Latency explains space complexity →

Also covered in

What to know first

Related concepts

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.