Space complexity

Time complexity gets the attention. Space is the one that takes a service down, because running out of memory is not "slower" — it is a heap dump, a long garbage-collection pause, and then a process that is gone.

#The same five million integers, two ways

### five million ints, two ways
###   int[]           18.9 MB
###   List<Integer>   95.4 MB

Five times, for identical data, and nothing about the second version looks wasteful in the source. List<Integer> is what you write when you want a list of numbers.

The arithmetic is worth doing once, because it explains a whole family of surprises. An int[] is five million slots of four bytes, contiguous — about 20 MB, and the measurement agrees. A List<Integer> is:

• five million Integer objects, each with a header and a field — 16 bytes each on a 64-bit JVM with compressed references, so 80 MB;
• plus a backing Object[] of five million references at 4 bytes each — 20 MB.

So a hundred megabytes to hold twenty megabytes of numbers, and the extra eighty is object headers and pointers. The primitives and wrappers lesson establishes where those 16 bytes come from; this is what they cost at scale.

#The three kinds of space, and only one is usually counted

When somebody says an algorithm is "O(1) space", they mean auxiliary space — extra memory beyond the input.

• Input space. The data you were given. Usually not counted, because you did not choose it.
• Auxiliary space. What the algorithm allocates itself. This is what O(1) or O(n) space refers to.
• The call stack. Counted, and routinely forgotten.

That last one is the one that bites, and it is the reason a recursive algorithm can be O(n) space when it allocates nothing at all:

long sum(int[] xs, int i) {
    if (i == xs.length) return 0;
    return xs[i] + sum(xs, i + 1);          // no allocation, O(n) space
}

Every call is a stack frame. A million elements is a million frames, and the result is a StackOverflowError — which, as the how-a-program-runs lesson explained, is a stack error rather than a heap one, and reports itself completely differently from running out of memory.

Java does not eliminate tail calls. Some languages turn that recursion into a loop; the JVM does not, and there is no flag that makes it. So in Java, recursion depth is a resource you are spending, and deep recursion over a large input is a loop waiting to be written.

#The trade you make on purpose

Most of the interesting choices in this course are time bought with space:

None is free, and stating the price is the part people skip. "Use a HashMap" costs a hash table the size of your data, and on a service with a heap budget that is a decision rather than a detail.

The reverse trade is rarer and real: streaming spends time to save space. Reading a file line by line is slower per element than having it all in memory, and it is the difference between a job that runs and a job that dies — which is the same argument the reading-input lesson made about BufferedReader.

#What "in place" means, and what it costs

An in-place algorithm uses O(1) auxiliary space — it rearranges the input rather than building a copy.

Collections.sort(list);           // sorts this list
List<T> sorted = list.stream()    // builds a new one
    .sorted().collect(toList());

Both are O(n log n) in time. The second allocates a second list, and for a large collection that is a real cost.

But in-place is not automatically the right answer, and the reason is not performance: it destroys the original. If anything else holds a reference to that list, you have changed their data too — the pass-by-value lesson's point arriving as a memory decision. A copy is often worth its space precisely because it is a copy.

#Measuring it, rather than reasoning about it

Reasoning gets you the shape. For an actual number:

• A heap dump and a tool that can read it — Eclipse MAT, VisualVM. It tells you what is there and what is holding it, which is usually the surprise.
• -Xmx deliberately low in a test, so the failure happens on your machine rather than in production.
• JOL (Java Object Layout) for the size of one object, if the arithmetic above matters to a decision.

The measurement at the top of this lesson was taken the crude way — total memory before and after, with a garbage collection either side — and that is enough to see a factor of five. It is not enough to see a factor of 1.1, and knowing which question you are asking decides which tool you need.