Space Complexity of Algorithms: Worked Examples

Space complexity tells you how much memory an algorithm needs as its input grows. In placement coding rounds, not knowing it is the fastest way to lose marks on a question you otherwise solved correctly.

What Space Complexity Measures

Space complexity is the total memory an algorithm requires as a function of its input size. That total has two components:

• Auxiliary space: extra or temporary memory the algorithm allocates while running (local variables, recursion stack, dynamically allocated arrays).
• Input space: memory occupied by the input data itself.

The formula is:

Space Complexity = Auxiliary Space + Input Space

A common source of confusion: when interviewers ask for space complexity during a technical round, they usually want the auxiliary space. Knowing the distinction helps you answer precisely.

Space complexity uses the same Big-O notation as time complexity. O(1) means constant memory: the algorithm’s memory footprint stays fixed no matter how large the input gets. O(n) means linear memory: double the input, roughly double the memory. The Big-O Cheat Sheet lists space complexity alongside time complexity for common algorithms, and it is worth bookmarking as a cross-reference during your preparation.

One more framing before the examples: high time complexity can slow a program down. High space complexity can prevent it from running at all, because the operating system will kill a process that exceeds its memory allocation. On Indian competitive programming judges, that verdict shows up as MLE (Memory Limit Exceeded).

How to Calculate Space Complexity: Four Worked Examples

The technique is the same every time: identify every variable and data structure the algorithm allocates, express each in terms of the input size n, sum them up, and drop constant factors.

Example 1: O(1) — Constant Space

int add(int a, int b) {
    int result = a + b;
    return result;
}

• Variables allocated: a, b, result — three integers.
• Memory per integer (32-bit system): 4 bytes.
• Total memory: 3 × 4 = 12 bytes.

No matter how large a and b are, the algorithm still allocates exactly three integers. The memory usage does not depend on the value or size of the input; it is a fixed constant. Space complexity: O(1).

Example 2: O(n) — Linear Space

int sumArray(int n) {
    int arr[n];     /* n integers */
    int i, sum = 0; /* 2 more variables */
    for (i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
        sum += arr[i];
    }
    return sum;
}

• Array arr: n × 4 bytes = 4n bytes.
• Variables n, i, sum: 3 × 4 = 12 bytes (constant).
• Total: 4n + 12 bytes.

As n grows, 12 becomes negligible; the dominant term is 4n. Drop the constant coefficient: space complexity is O(n).

Example 3: O(log n) — Logarithmic Space (Recursive Binary Search)

int binarySearch(int arr[], int low, int high, int target) {
    if (low > high) return -1;
    int mid = (low + high) / 2;
    if (arr[mid] == target) return mid;
    if (arr[mid] < target)
        return binarySearch(arr, mid + 1, high, target);
    return binarySearch(arr, low, mid - 1, target);
}

Each recursive call adds one frame to the call stack. That frame contains low, high, mid, target, and the pointer to arr (a constant amount of memory per call).

How many calls can be active simultaneously? Each call halves the search range. Starting from n elements:

• After 1 call: n/2 elements remain.
• After 2 calls: n/4 elements remain.
• After k calls: n / 2^k elements remain.

The recursion bottoms out when n / 2^k = 1, which gives k = log₂(n). At most log₂(n) frames are on the stack at any moment. Space complexity: O(log n).

Example 4: O(n²) — Quadratic Space

void initMatrix(int n) {
    int matrix[n][n]; /* n rows, n columns */
    int i, j;
    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++)
            matrix[i][j] = 0;
}

• Array matrix[n][n]: n × n × 4 bytes = 4n² bytes.
• Variables n, i, j: 12 bytes (constant).
• Total: 4n² + 12 bytes — O(n²).

This pattern appears any time you allocate a two-dimensional structure proportional to the input: adjacency matrices, DP tables for two independent dimensions, distance matrices for graph algorithms. See the matrix operations programs article for worked implementations; the O(n²) space cost of a 2D array appears directly in those examples.

Space Complexity Classes: Quick Reference

Class	Name	When it appears	Placement judge outcome (256 MB limit, n = 10⁵)
O(1)	Constant	Fixed variables, in-place swap, two-pointer technique	Passes comfortably
O(log n)	Logarithmic	Recursive binary search, balanced BST operations	Passes comfortably
O(n)	Linear	Single array, recursion on linear structure, hash table	Passes for n up to ~10⁷ integers
O(n²)	Quadratic	2D arrays, adjacency matrix, 2D DP table	MLE for n above ~10⁴
O(2^n)	Exponential	Subset enumeration, brute-force exhaustive search	MLE for n above 25 to 30

This table assumes 4 bytes per integer. The data structures programs reference covers concrete implementations for arrays, linked lists, and stacks if you want to trace through memory allocation for each.

The Merge Sort Space Complexity Misconception

A persistent error in legacy placement content (including many textbook summaries and older online articles) is listing merge sort’s space complexity as O(n log n). That number is merge sort’s time complexity.

Here is the correct derivation:

• Auxiliary array: The merge step combines two sorted halves into one. It needs a temporary array of size n to hold the merged result. That is O(n) auxiliary space.
• Recursion stack: Merge sort splits in half at each level. Maximum recursion depth is log₂(n) levels. Each stack frame uses O(1) space. Stack total: O(log n).
• Combined: O(n) + O(log n) = O(n), because n grows faster than log n.

Standard merge sort: O(n) space complexity.

Quick sort (in-place, choosing a random pivot) uses O(log n) average stack space because of its recursion depth. Its worst case is O(n) when the array is already sorted and the first element is always chosen as the pivot. The recursion degenerates into n levels in that scenario.

If you see “merge sort: O(n log n) space” anywhere in your preparation material, treat it as a signal to double-check the source’s time-space figures. The data structures interview questions article covers merge sort’s time complexity at length; they are different quantities.

Reducing Space Complexity in Practice

Four techniques that come up repeatedly in placement code reviews and technical interviews:

• Use in-place algorithms. Reversal of an array can be done with a two-pointer approach in O(1) space; no auxiliary array needed. Many sorting and partitioning operations have in-place variants. The trade-off is usually code complexity, not time complexity.
• Replace recursion with iteration. Recursive functions consume stack space proportional to their depth. An iterative binary search uses O(1) space; a recursive one uses O(log n). For deep recursion (DFS on a graph with large inputs), the difference between O(n) stack and a manual O(n) queue can determine whether the program runs at all.
• Reuse variables. Declaring a new variable inside a loop body is usually fine (most compilers optimize this), but allocating a new array inside a loop body compounds with the loop count. A single pre-allocated buffer reused across iterations can cut O(n²) allocation patterns to O(n).
• Choose the right data structure. An adjacency matrix costs O(V²) space for V vertices. An adjacency list costs O(V + E), far cheaper for sparse graphs. The choice matters when V = 10⁵ and E = 10⁵: a matrix needs 10¹⁰ cells; a list needs roughly 2 × 10⁵.

Space Complexity in Placement Tests

Most coding rounds at Indian IT companies (TCS NQT, Infosys Hackwithinfy, AMCAT Automata) have two evaluation layers: correctness and efficiency. Efficiency means both time and space.

What to expect in practice:

• The problem statement usually specifies a memory limit (commonly 256 MB). An O(n²) solution for n = 10⁵ needs roughly 40 GB for a 2D integer array, far above the limit.
• Panel interviews at product companies almost always ask for the space complexity of the solution you just coded. Stating O(n) time without O(1) space is an incomplete answer.
• Optimisation follow-ups are common: “You solved it in O(n) space. Can you reduce that to O(1)?” This tests whether you understand the algorithm deeply enough to use the two-pointer or sliding-window technique instead of an auxiliary array.

Going in prepared on space complexity is a small edge. Most students who have practiced DSA on competitive programming platforms can state time complexity reflexively. Space complexity is the gap.

The O(1) versus O(n) trade-off you worked through in the examples above is not just exam content. LLM applications manage context windows the same way: keep every prior message in memory (memory grows with conversation length, an O(n) pattern) or cap the window to a fixed size (a constant-space approach). TinkerLLM at ₹299 is where that trade-off stops being theoretical. You build and deploy an LLM-backed project and see memory constraints play out in a runtime you control, not in pseudocode.