Space complexity in Java

Problem

The export that eats the memory

Every night a service exports the shop's logs for the day to an archive. So that it can carry on from where it stopped after a crash, it writes a checkpoint after every line. Except that the checkpoint is a copy of the whole file so far:

static long exportLogs(List<String> logs) {
    List<String> file = new ArrayList<>();
    List<List<String>> checkpoints = new ArrayList<>();
    for (String line : logs) {
        file.add(line);
        checkpoints.add(new ArrayList<>(file));
    }
    long places = 0;
    for (List<String> saved : checkpoints) {
        places += saved.size();
    }
    return places;
}

How many places do the copies hold? The program counts them:

for (int n : new int[] {5, 1000}) {
    List<String> logs = new ArrayList<>();
    for (int i = 1; i <= n; i++) {
        logs.add("line " + i);
    }
    System.out.println(n + " lines: " + exportLogs(logs) + " places");
}

5 lines: 15 places
1000 lines: 500500 places

For 1000 lines it is 500 500 places. The logs of one day are 100 000 lines, and that is 5 000 050 000 places. Every place holds a reference of 4 to 8 bytes: between 20 and 40 GB just for the copies. In the test with 1000 lines everything passes, and at night the export stops with OutOfMemoryError.

The idea

Memory is a cost too

So far you counted operations. Memory is counted the same way: how many places the algorithm sets aside itself, apart from the input it receives. This is the space complexity of the algorithm. It is written with Big-O too:

O(1): a few variables, however big the input;
O(n): a copy of the input, a helper list, a set with all the elements;
O(n²): a copy of the copy at every step, as in the export.

The input does not count, because it exists without the algorithm. Neither does the result the task asks for: the file with n lines is the export's job. What counts are the copies it makes along the way.

See it

The copies stay

List<String> file = new ArrayList<>();
int checkpoint = 0;
for (String line : logs) {
    file.add(line);
    checkpoint = file.size();
}

Step by step, in words

file is the file the export writes; logs has 4 lines. checkpoints keeps where to resume after a crash.
Line 1 goes into the file. The checkpoint is a copy of the whole file: 1 place.
Line 2. The new checkpoint copies both lines, and the old one stays in the list: 1 + 2 = 3 places.
After 4 lines memory holds 1 + 2 + 3 + 4 = 10 places. After n lines it is n(n + 1)/2: five billion for 100 000 lines.
To resume after a crash you only need how far you got. The copies go; one number stays.
Every line changes the number: checkpoint = 4. The extra memory is 1 place, however many lines there are.

Every copy is a new list in memory, and nobody deletes the old ones: the list checkpoints keeps them. That is why the places grow as 1 + 2 + 3 + … + n. To carry on after a crash, the export only needs how far it got:

static int exportLogs(List<String> logs) {
    List<String> file = new ArrayList<>();
    int checkpoint = 0;
    for (String line : logs) {
        file.add(line);
        checkpoint = file.size();
    }
    return checkpoint;
}

for (int n : new int[] {5, 1000}) {
    List<String> logs = new ArrayList<>();
    for (int i = 1; i <= n; i++) {
        logs.add("line " + i);
    }
    System.out.println(n + " lines, checkpoint: " + exportLogs(logs));
}

5 lines, checkpoint: 5
1000 lines, checkpoint: 1000

The file is the same, and the extra memory is one number: O(1) instead of O(n²).

Try it

Predict the output

The export with the copies gets 6 lines. How many places do the checkpoints hold?

static long exportLogs(List<String> logs) {
    List<String> file = new ArrayList<>();
    List<List<String>> checkpoints = new ArrayList<>();
    for (String line : logs) {
        file.add(line);
        checkpoints.add(new ArrayList<>(file));
    }
    long places = 0;
    for (List<String> saved : checkpoints) {
        places += saved.size();
    }
    return places;
}

for (int n : new int[] {6}) {
    List<String> logs = new ArrayList<>();
    for (int i = 1; i <= n; i++) {
        logs.add("line " + i);
    }
    System.out.println(n + " lines: " + exportLogs(logs) + " places");
}

Answer

6 lines: 21 places

6 lines: 36 places

6 lines: 6 places

See it

A copy or in place

The admin wants the newest log lines first. There are two ways. One makes a new list in reverse order, and the other swaps the elements in the list itself: the first with the last, the second with the one before last, until the two ends meet.

static List<String> newestFirst(List<String> logs) {
    List<String> result = new ArrayList<>();
    for (int i = logs.size() - 1; i >= 0; i--) {
        result.add(logs.get(i));
    }
    return result;
}

static void reverseInPlace(List<String> logs) {
    int left = 0;
    int right = logs.size() - 1;
    while (left < right) {
        String saved = logs.get(left);
        logs.set(left, logs.get(right));
        logs.set(right, saved);
        left++;
        right--;
    }
}

List<String> logs = new ArrayList<>(List.of("09:00 login", "09:05 cart", "09:07 payment"));
List<String> newest = newestFirst(logs);
System.out.println("Copy:     " + String.join(", ", newest));
System.out.println("Original: " + String.join(", ", logs));
reverseInPlace(logs);
System.out.println("In place: " + String.join(", ", logs));

Copy:     09:07 payment, 09:05 cart, 09:00 login
Original: 09:00 login, 09:05 cart, 09:07 payment
In place: 09:07 payment, 09:05 cart, 09:00 login

The copy needs n new places, but the original stays as it was. The change in place needs one place for the swap, but the old order is gone. Which is better depends on whether someone else still reads the original.

More precisely, if you are curious

The built-in functions make the same choice, and the name does not always tell you:

List<String> logs = new ArrayList<>(List.of("09:00 login", "09:05 cart", "09:07 payment"));
List<String> view = logs.reversed();
List<String> copy = new ArrayList<>(view);
Collections.reverse(logs);
System.out.println("In place: " + String.join(", ", logs));
System.out.println("Copy:     " + String.join(", ", copy));

In place: 09:07 payment, 09:05 cart, 09:00 login
Copy:     09:07 payment, 09:05 cart, 09:00 login

Collections.reverse reverses in place. logs.reversed() (since Java 21) copies nothing: it is a view that reads the same list from the back. The copy happens only with new ArrayList<>(...). The same holds for subList: a view, not a copy.

The copy is shallow: the new list keeps references to the same texts, not new texts. That is why the places are counted one per element.

Try it

Fill in

Finish the swap of the two ends:

String saved = logs.get(left);
logs.set(left, logs.get(right));
logs.set(right, );

First the value on the left is kept in saved, because the next line overwrites it. Then it goes to the place on the right.

See it

Recursion holds memory too

A list is not the only thing that takes room. Every call of a method keeps its parameters and local variables on the call stack until it returns. Here is counting the errors in the log with recursion and with a loop:

static int errorsFrom(List<String> logs, int i) {
    if (i == logs.size()) {
        return 0;
    }
    int here = logs.get(i).startsWith("ERROR") ? 1 : 0;
    return here + errorsFrom(logs, i + 1);
}

static int errors(List<String> logs) {
    int count = 0;
    for (String line : logs) {
        if (line.startsWith("ERROR")) {
            count++;
        }
    }
    return count;
}

List<String> small = makeLogs(500);
List<String> big = makeLogs(1_000_000);
System.out.println("500 lines: " + errorsFrom(small, 0) + " errors");
try {
    System.out.println("1000000 lines: " + errorsFrom(big, 0) + " errors");
} catch (StackOverflowError e) {
    System.out.println("1000000 lines: StackOverflowError");
}
System.out.println("With a loop: " + errors(big) + " errors");

500 lines: 5 errors
1000000 lines: StackOverflowError
With a loop: 10000 errors

The recursion makes not a single list, but for n lines there are n unfinished calls on the stack: O(n) memory. The stack is small, and a million calls do not fit. The loop has one variable count: O(1).

More precisely, if you are curious

How deep the recursion can go depends on the size of the stack and the size of one frame. In Java the stack of a thread is 1 MB by default and is changed with -Xss (the site's check runs the programs with 8 MB, and it is still not enough). StackOverflowError is an Error, not an Exception: here we catch it so you can see the name, and in real code the recursion is rewritten as a loop.

When the recursive call is the last action of the function (with no here + after it), some languages turn it into a loop (a tail call). Java, C#, Python and Node do not, so in them depth always costs memory.

The idea

Time against memory

The shop checks whether two orders of the day have the same number. The first way compares every pair. The second remembers the numbers it has seen in a set:

static boolean hasDuplicateLoops(int[] orders) {
    for (int i = 0; i < orders.length; i++) {
        for (int j = i + 1; j < orders.length; j++) {
            if (orders[i] == orders[j]) {
                return true;
            }
        }
    }
    return false;
}

static boolean hasDuplicateSet(int[] orders) {
    Set<Integer> seen = new HashSet<>();
    for (int order : orders) {
        if (!seen.add(order)) {
            return true;
        }
    }
    return false;
}

int[] today = {100512, 100513, 100514, 100512};
System.out.println(hasDuplicateLoops(today) + " " + hasDuplicateSet(today));

true true

Both give the same answer, but they pay differently:

the nested loops: O(1) memory and O(n²) time;
the set: O(n) memory (up to n numbers) and O(n) time.

This is a common trade: memory for time. How many comparisons and checks the two make when there is no repeat (the worst case):

static long comparisonsLoops(int[] orders) {
    long count = 0;
    for (int i = 0; i < orders.length; i++) {
        for (int j = i + 1; j < orders.length; j++) {
            count++;
            if (orders[i] == orders[j]) {
                return count;
            }
        }
    }
    return count;
}

static long checksSet(int[] orders) {
    Set<Integer> seen = new HashSet<>();
    long count = 0;
    for (int order : orders) {
        count++;
        if (!seen.add(order)) {
            return count;
        }
    }
    return count;
}

for (int n : new int[] {10, 1000}) {
    int[] orders = new int[n];
    for (int i = 0; i < n; i++) {
        orders[i] = 100000 + i;
    }
    System.out.println(n + " orders: " + comparisonsLoops(orders) + " comparisons with loops, " + checksSet(orders) + " checks with a set");
}

10 orders: 45 comparisons with loops, 10 checks with a set
1000 orders: 499500 comparisons with loops, 1000 checks with a set

Nested loops, no memory O(n²)
A set of seen numbers, n places O(n)

Algorithm	n = 10	n = 1,000	n = 100,000
Nested loops, no memory	45	499,500	≈ 4,995,000,000
A set of seen numbers, n places	10	1,000	100,000

The code runs in your browser, in JavaScript. The number of operations is the same in every language, because the algorithm is the same. The time depends on the machine, so it is only for comparison. “≈” is an estimate from the curve: we do not run an n that big, so the page does not freeze.

For 100 000 orders the loops make almost 5 billion comparisons, and the set makes 100 000 checks and keeps 100 000 numbers. When the memory is there, the set wins. When it is not (a small device, a huge input), you either sort the numbers (then the repeats are next to each other) or read in parts.

More precisely, if you are curious

We count one check in the set as one operation. It is O(1) on average, because the set is a hash table: the number becomes a hash, and the hash says which bucket to look in. One place in a set costs more than one number in an array: in a HashSet<Integer> about 40–50 bytes (an Integer object and an entry in the table). So "O(n) memory" for 10 million orders is hundreds of MB, not 40.

Try it

Find the bug

A colleague rewrote the check with a set, but it never finds a repeat:

static boolean hasDuplicateSet(int[] orders) {
    for (int order : orders) {
        Set<Integer> seen = new HashSet<>();
        if (!seen.add(order)) {
            return true;
        }
    }
    return false;
}

int[] today = {100512, 100513, 100514, 100512};
System.out.println(hasDuplicateSet(today));

false

Number 100512 is there twice, and the answer is "no". Which line is the bug on?

Pick the line with the bug.

Exercise

The last three lines

Solve the task in your editor.

The last lines. When something breaks, the admin wants only the last k lines of the log. Write lastLines(logs, k), which returns them while keeping at most k lines in memory, not the whole log: O(k) memory. Run it with 1000 lines ("line 1" … "line 1000") and k = 3.

line 998
line 999
line 1000

One possible solution

Keep a queue: every new line goes in at the back, and when there are more than k lines, the oldest goes out at the front.

static List<String> lastLines(List<String> logs, int k) {
    ArrayDeque<String> recent = new ArrayDeque<>();
    for (String line : logs) {
        recent.addLast(line);
        if (recent.size() > k) {
            recent.removeFirst();
        }
    }
    return new ArrayList<>(recent);
}

More tasks

The average length without a copy. Compute the average length of a line in the log with O(1) extra memory: without a new list of lengths.
Errors by hour. Count the errors for every hour (09, 10…). How much memory does your solution need if there are 24 hours and a million lines?
The repeated numbers. Return not only "yes or no", but all repeated numbers. How much memory does the solution with a set need, and can you do without it?

Test

Check yourself

1. A function makes a new list with n log lines in reverse order. How much extra memory does it need?O(1)O(n)O(n²)

2. The export keeps a copy of the whole file so far after every line. How many places does memory hold for n lines?n(n + 1)/2, that is O(n²)n2n

3. A recursive function with no list at all calls itself 1 000 000 times, one call inside another. How much memory does it need?O(n): every call stays on the stack until it returnsO(1), because there are no listsNone, memory is only for objects

4. You look for a repeated number in 10 000 000 orders on a server with a few GB of free memory. Which do you choose?It makes no differenceThe set: O(n) memory, but O(n) time instead of O(n²)The nested loops, because they need no memory

5. What does not count in the extra memory of a function?The stack of its recursionA copy of the input the function makesThe input the function receives

Space complexity

Cookies