تعقيد المساحة

Written Explanation

What counts

Space complexity is how the extra memory an algorithm needs grows with the input size n. "Extra" means memory beyond the input itself: new arrays, new collections, and the call stack of nested method calls. The input is already there whatever you do, so it is not counted. (Some texts count it; always check which convention is meant. This course counts the extra memory only.)

We use the same notation as for time:

Counting memory in bytes is a separate, lower-level question. Big O ignores the constant, just as it ignored the cost of a single step: a HashSet<Integer> of n numbers uses noticeably more bytes per number than an int[], but both are O(n).

O(1) space: a few variables

static int maxOf(int[] a) {
    int m = a[0];
    for (int x : a) if (x > m) m = x;
    return m;
}

The method uses m and the loop variable, no matter how long a is: O(1) space. Its time is O(n). Time and space are separate questions with separate answers.

O(n) space: a copy of the input

Reversing an array has two natural solutions:

static int[] reverseCopy(int[] a) {
    int[] r = new int[a.length];                 // new array of size n
    for (int i = 0; i < a.length; i++) r[a.length - 1 - i] = a[i];
    return r;
}

static void reverseInPlace(int[] a) {
    for (int i = 0, j = a.length - 1; i < j; i++, j--) {
        int t = a[i]; a[i] = a[j]; a[j] = t;    // swap the two ends, move inward
    }
}

With {4, 8, 15, 16, 23, 42} both produced [42, 23, 16, 15, 8, 4]. But reverseCopy left the original unchanged and used O(n) extra space, while reverseInPlace changed the original and used only t, i, and j: O(1) space. Both take O(n) time.

In place means the algorithm rearranges the data where it already is and needs only O(1) extra memory. The price is that the input is changed.

Recursion uses memory for the call stack

Each call to a method creates a stack frame (BEG-038), and a recursive call waits on the stack until the call below it returns. A recursive method with depth n therefore needs O(n) stack space even if it declares no arrays:

static long sumTo(int n) { return n == 0 ? 0 : n + sumTo(n - 1); }   // O(n) stack space
static long sumLoop(int n) { long s = 0; for (int i = 1; i <= n; i++) s += i; return s; } // O(1)

Both compute the same thing. sumTo(1000) returned 500500 and sumLoop(100_000) returned 5000050000. When I called sumTo(1_000_000) on JDK 21 with default settings, it threw StackOverflowError, the error from BEG-038: a million waiting frames did not fit. (The depth at which this happens depends on the JVM's stack size setting and on the frame size, so I will not quote a limit.) The loop version has no such problem.

Trading space for time

Often one resource can be bought with the other. Duplicate detection shows it:

The second solution is much faster for large n, and it pays for the speed with a set that can hold all n items. The first uses almost no memory and is slow. Neither is "correct" in the abstract: you choose by what is scarce in your situation. L06 builds and times both.

Another familiar trade is a cache: you keep results in memory (space) to avoid recomputing them (time).