Space Complexity

DSA · Introduction to DSA

Theory

Space complexity measures how much extra memory an algorithm needs as the input grows, again written in Big O. It counts auxiliary space such as new arrays, hash tables and the recursion call stack, not usually the input itself. Reversing a list in place uses O(1) extra space, while building a reversed copy uses O(n). Recursive algorithms use stack space proportional to their recursion depth.

Why we use it

Memory is limited, especially on mobile devices, in serverless functions and when processing big data. Many problems have a time-space trade-off: you can often run faster by storing more (for example memoisation or hash tables).

When to use it

Consider space whenever you create copies of data, use recursion, cache results, or work with data that may not fit in memory.

How it works

  1. Start
  2. List extra variables, arrays and structures created
  3. Include recursion stack depth
  4. Does extra memory grow with n? Yes: Space is O(n) or more. No: Space is O(1).
  5. Report auxiliary space (exclude the input itself)

Syntax

O(1)   a few variables (in-place swap, two pointers)
O(n)   a copy of the input, a hash map of n items
O(n²)  a 2-D table such as an n x n DP grid
Recursion depth d  ->  O(d) stack space

Example

def reverse_copy(arr):
    return arr[::-1]            # O(n) extra space

def reverse_in_place(arr):
    i, j = 0, len(arr) - 1      # O(1) extra space
    while i < j:
        arr[i], arr[j] = arr[j], arr[i]
        i += 1
        j -= 1
    return arr

data = [1, 2, 3, 4, 5]
print("Copy:", reverse_copy(data), "original kept:", data)
print("In place:", reverse_in_place(data))

Key points

DSA topics

Introduction to DSA

Arrays and Searching

Sorting Algorithms

Linked Lists

Stacks and Queues

Hashing

Trees

Heaps

Graphs

Algorithm Techniques

Classic Algorithms

Dynamic Programming

T
Tech Town
Log InSign Up Free
Home SQL Python DSA Power BI Snowflake Databricks Spark Gen AI Practice Problems Contest Blog

Data Structures & Algorithms

The complete DSA roadmap: theory, why and when to use every structure and algorithm, Big O complexity, and Python code you can run right here in the browser.

{{ sectionCount }}
Sections
{{ topicCount }}
Topics
Free
Forever
Hands-on practice Practice DSA Online 251 problems across 13 patterns, with hidden tests and step-by-step optimal solutions. Start practising →
Section {{ sec.num }}

{{ sec.label }}

DSA  /  {{ current.sectionLabel }}  /  {{ current.name }}

{{ current.name }}

Theory

{{ current.def }}

Why we use it

{{ current.why }}

When to use it

{{ current.when }}

Flowchart — how {{ current.name }} works
{{ nd.text }}
{{ nd.text }}
◇ {{ nd.text }}
Yes → {{ nd.yes }}
No → {{ nd.no }}
Step-by-step visualisation
{{ cell.v }}
{{ cell.i }} {{ cell.tag }}
Step {{ vizStepLabel }}: {{ vizNote }}
■ comparing ■ swapping / moving ■ done / found ■ out of range
Complexity & Pseudocode
{{ current.syntax }}
Example Code
{{ current.example }}
▶ Try It Live — runs real Python 3 in your browser (first run loads the engine)
{{ liveOutput }}
{{ liveError }}
Key Points — click to check off as you learn
  • {{ pt.mark }} {{ pt.text }}

Share this topic