Computer Science

Space Complexity, explained

Space complexity describes how much memory an algorithm needs as input size grows.

Back to Glossary

Part of the Semantic Notion technical glossary.

Short Definition

Space complexity describes how much memory an algorithm needs as input size grows.

Intuition

A fast method can still fail if it needs too much memory.

Technical Definition

Space complexity is the asymptotic memory required by an algorithm, including auxiliary data structures and sometimes input storage depending on convention.

Example

A dynamic programming algorithm may trade extra memory for faster computation.

Common Misunderstandings

Low time complexity does not imply low memory use.

Memory access patterns can matter as much as total memory volume.

Same Category

More from Computer Science

AlgorithmAn algorithm is a precise procedure for solving a problem or computing a result.Byzantine Fault ToleranceByzantine fault tolerance is the ability of a distributed system to keep working even when some nodes behave arbitrarily or maliciously.CacheA cache stores recently or frequently used data in a faster location so future access is quicker.Cache CoherenceCache coherence is the property that multiple caches maintain a consistent view of shared data.CAP TheoremCAP theorem says a distributed data system cannot simultaneously guarantee consistency, availability, and partition tolerance during a network partition.ConcurrencyConcurrency is the ability of a system to make progress on multiple tasks during overlapping time periods.

Essays that use this concept

System ProgrammingCache Coherence and Synchronization: Ensuring Data Consistency in Multi-Core Systems

Start here

Need the broader concept map?

Return to the glossary index to move from this definition into adjacent AI, ML, mathematics, and computer science terms.

Browse Glossary