Skip to main content

Space Complexity

Learn Space Complexity (Complexity, Programming Fundamentals) with worked examples, diagrams and interview questions. Free on JavaSchoolLab.

What is Space Complexity? Space complexity measures how much extra memory an algorithm needs, relative to the input size n . Just like time complexity, we express it using Big-O notation — O(1), O(n), O(n^2), etc. Total memory usage has two parts: • Input space — the memory taken by the input itself (usually not counted). • Auxiliary space — the EXTRA memory the algorithm allocates while running (this is what "space complexity" almost always refers to). When people say "this algorithm is O(n) space", they mean it uses auxiliary space proportional to n, beyond the input it was given.

More lessons in Complexity