Space complexity
Space complexity measures how the memory or storage required by an algorithm grows as a function of input size.
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.
Related concepts
- performancemeasured by · 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.
- quantizationaddressed by · Quantization maps numerical values to a finite set of discrete representations, often using reduced precision to lower model storage or computation requirements.
- memorymeasures · Memory is a storage resource or mechanism that retains data or computational state for access during computation or later use.
- storage capacitymeasures · Storage capacity is the amount of persistent data a storage resource can hold or has available for use.
- constant timecontrasts with · Constant time is an asymptotic complexity in which the running time remains bounded independently of input size, conventionally denoted O(1).
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.