Introduction to Space Complexity

Input storage is not automatically auxiliary space

Space complexity describes how the memory use of an algorithm grows as the input size n grows. For the array [4, 2, 7, 1], the four slots holding those values are input space. They belong to the data given to the algorithm, not to the memory requested by the summing steps themselves.

Total space includes the input array and every extra value used while the algorithm runs. Auxiliary space reports only the extra working memory requested by the algorithm, excluding the input space. The array still consumes real memory, but a claim such as O(1) auxiliary space says that the algorithm adds only a fixed amount beyond the array.

Reusing sum and i keeps extra space fixed as n grows

The direct method reads each input slot and reuses two working variables: i for the current index and sum for the running total. It does not create a new stored value for each array element.

int sum = 0;
for (int i = 0; i < n; i++) {
    sum += arr[i];
}

For [4, 2, 7, 1], i visits indices 0 through 3 and sum changes from 0 to 4, 6, 13, and 14. If the input grows, the loop makes more visits, but it still needs only i and sum. The number of working variables stays fixed, so the direct method uses O(1) auxiliary space.

Copying every value makes extra space grow with n

A copy-first method creates a separate buffer and places every input value into it before summing. For the running input, the buffer receives 4, then 2, then 7, then 1. It has four occupied slots before the final sum is computed.

int buffer[n];
for (int i = 0; i < n; i++) {
    buffer[i] = arr[i];
}

int sum = 0;
for (int i = 0; i < n; i++) {
    sum += buffer[i];
}

The original array remains input space, while the buffer is auxiliary space. There is one buffer slot per input value, so an input of size n requires n extra slots. The fixed variables i and sum do not change that growth, making the copy-first method O(n) auxiliary space.

The largest live memory snapshot determines the space cost

Space is measured by the largest amount of storage that is live at the same time. You do not add memory for every read, assignment, or loop iteration. The same sum cell is reused after each read, so its repeated updates do not create repeated storage.

At the direct method's peak, the input array [4, 2, 7, 1] is live together with the fixed cells i and sum. Its auxiliary part stays fixed, even though the loop visits four slots and ends with sum equal to 14.

At the copy-first method's peak, the original input array, the four-slot buffer, and the fixed cells i and sum are live together. For a general input of size n, that snapshot contains the input space, n auxiliary buffer slots, and fixed working space. The growing part is the buffer, so the auxiliary cost is O(n).