Linear Space On

Linear Space — O(n)

Imagine you're handed a stack of n exam papers and told to grade them. If you can grade each paper and hand it straight back without keeping anything, you use almost no extra desk space no matter how tall the stack. But if the rule is "make one photocopy of every paper before returning any of them," then a stack twice as tall needs twice as many photocopies — your desk fills up in direct proportion to the input. That proportional growth is exactly what linear space, written O(n), describes: the extra memory an algorithm needs grows as a straight-line function of the input size.

Precise definition

Let n be the size of the input and let S(n) be the amount of auxiliary memory the algorithm allocates while running — the working memory beyond the input itself. We say the algorithm uses linear space when S(n) = O(n): there exist constants c > 0 and n0 such that S(n) ≤ c·n for all n ≥ n0.

Two clarifications matter for interviews:

• Auxiliary vs. total. Auxiliary space excludes the input. If a function copies its n-element input into a new array, that's O(n) auxiliary. Total space would be the input plus auxiliary.
• Constants and lower terms vanish. Storing 3n + 100 integers is still O(n). Big-O captures the shape of growth, not the exact count. So O(n), O(2n), and O(n + 50) are the same class.

Worked example — counting the allocations

Consider building a frequency map, then returning the elements that appear exactly once, in order. Input is an array a of n integers.

Trace it on a = [4, 7, 4, 2, 7, 9], so n = 6:

• Step 1 — build the count map. Walk the array once, incrementing a hash-map entry per value. After the pass the map holds one entry per distinct value: {4:2, 7:2, 2:1, 9:1} — here 4 entries. In the worst case every value is distinct, so the map holds n entries. Cells used so far: up to n.
• Step 2 — collect the singletons. Walk the map, appending values whose count is 1 into a result list: [2, 9]. In the worst case (all distinct) every element is a singleton, so this list can also grow to n entries.

Peak auxiliary memory = map (≤ n) + result list (≤ n) = 2n cells in the worst case. Drop the constant → O(n) space. The two loops each touch every element a constant number of times, so time is O(n) too — but notice space and time are counted separately: space asks "how many cells are alive at the peak?", not "how many operations ran?"

Common pitfalls — what an interviewer probes

• Forgetting the output counts. If you allocate a result array of size n, that's O(n) space even if your "scratch" variables are O(1). Interviewers often ask "can you do it in O(1) extra space?" — meaning ignore the required output and mutate in place.
• Hidden recursion stack. A recursive function that recurses to depth n uses O(n) stack space even with no explicit array. Classic trap: naive recursion over a linked list, or quicksort's worst-case O(n) recursion depth. The call stack is real memory.
• Confusing space with time. An O(n) time algorithm can use O(1) space (e.g. a running sum), and an O(1)-per-step loop can still hoard O(n) space if it buffers everything. Always count them independently.
• Data-dependent size. The hash-map example is O(n) in the worst case (all distinct) but can be O(1) in the best case (all identical → one entry). State which case you mean; interviewers reward that precision.

When it matters — trade-offs vs. neighbouring classes

Linear space is usually the comfortable default: you can afford one pass' worth of bookkeeping, and it unlocks big time savings. The canonical trade is the hash-map trick — spend O(n) space to turn an O(n²) brute-force search into O(n) time (e.g. two-sum with a seen-set). You're buying speed with memory.

Against its neighbours:

• vs. O(1) constant space: O(1) is strictly better on memory and is demanded when data won't fit in RAM or on tiny embedded devices. But squeezing to O(1) often costs time or requires mutating the input — not always allowed.
• vs. O(log n): O(log n) space (e.g. balanced-tree recursion, binary search's implicit stack) is far more frugal — a billion elements need ~30 cells, not a billion. Prefer it when memory is the bottleneck.
• vs. O(n log n) / O(n²) space: these appear in DP tables and memoization. O(n) space is the ceiling you fight to stay under; a common interview upgrade is collapsing a 2-D DP table (O(n²)) into a rolling 1-D array (O(n)).

Practical scale check: O(n) space for n = 10⁹ 32-bit ints is ~4 GB — often too much. That's why streaming/one-pass O(1)-space algorithms exist for huge inputs.

Key takeaways

• O(n) space means auxiliary memory grows proportionally to input size: double the input, double the memory — a straight line through the origin.
• Count peak live memory, drop constants and lower terms; 2n + 100 cells is still O(n). Space and time are measured independently.
• Watch the hidden costs interviewers probe: output arrays, recursion-stack depth, and best-vs-worst-case size for data-dependent structures like hash maps.
• It's the sweet-spot default — trade O(n) memory to cut time (hash-map trick) — but drop to O(1)/O(log n) when data is huge, and collapse O(n²) DP tables to O(n) when you can.