15% off all plans & roadmaps Use code
See plansOpening your learning path
Progress is saved as you study.
Space complexity measures the memory an algorithm holds while it runs, as the input size n grows. Auxiliary space is the extra memory beyond the given input, and you state whether a newly built output counts. A new array of n values costs O(n) extra space. A fixed number of reused variables costs O(1).
| Given input | n values, reported separately, not auxiliary space |
|---|---|
| Scalar variables | i and currentValue: a fixed count, so O(1) |
| New output array | Grows from 0 to n values, so O(n) |
| Convention A | Count the output: O(n) additional storage |
| Convention B | Exclude the output: O(1) non-output auxiliary space |
| Time of doubleValues | O(n), one fixed-cost iteration per item |
The lesson assumes you can already describe how an algorithm’s running time grows with input length.
Measure a different resource: memory used while the algorithm runs.
For an input array items, separate memory into these categories:
items.A fixed number of scalar variables remains constant-sized as n grows. A new array that grows to contain one value per input item grows linearly.
When discussing memory during execution, measure peak live memory: the largest amount of relevant memory held at one time.
These resource-analysis ideas follow standard algorithm-analysis foundations: MIT 6.006 Introduction to Algorithms and Introduction to Algorithms.
Use this input throughout:
1items = [4, 1, 7]The goal is to build a separate array named doubled:
1doubled = [8, 2, 14]Before work begins, distinguish what already exists from what the algorithm creates.
| Array | Indices | Values | Storage role |
|---|---|---|---|
items | 0, 1, 2 | [4, 1, 7] | Given input |
doubled | none yet | [] | New output |
The input has length 3. The new output begins at length 0.
The name doubled is one scalar reference, but the collection it refers to stores multiple values. Count the stored values in the collection, not just the variable name.
Start at index 0. On each iteration, read one input value, multiply it by 2, append the result, and move to the next index.
While the loop runs, items stays as given, doubled gains one value per input item (length 0 to 3), and the scalars i and currentValue stay a fixed count.
| State | items | i | Value read | doubled | Extra collection length |
|---|---|---|---|---|---|
| State 0 | [4, 1, 7] | 0 | none | [] | 0 |
| State 1 | [4, 1, 7] | 1 | items[0] = 4 | [8] | 1 |
| State 2 | [4, 1, 7] | 2 | items[1] = 1 | [8, 2] | 2 |
| State 3 | [4, 1, 7] | 3 | items[2] = 7 | [8, 2, 14] | 3 |
The memory behavior has two parts:
items stays [4, 1, 7]. It was supplied to the algorithm and is not changed.doubled grows by one stored value per iteration.The scalar variables do not grow this way:
i holds one index.currentValue holds one input value.Their contents change, but the algorithm still has only a fixed number of scalar storage locations.
At the start of each iteration, pause before reading items[i].
At that moment, doubled already contains the correct doubled values for every earlier input position.
For this example:
i = 0, no input values have been processed, so doubled = [].i = 1, the first input value has been processed, so doubled = [8].i = 2, the first two input values have been processed, so doubled = [8, 2].i = 3, all three input values have been processed, so doubled = [8, 2, 14].The loop invariant is:
At the start of iteration
i,doubledcontains exactly 2 times each of the firstiinput items, in the same order.
The invariant describes correctness and output growth. If i input items have been processed, then doubled has exactly i values.
Let n be the length of items.
To maintain the invariant:
i to 0.i < n, read items[i].doubled.i by 1.i = n, every input item has been processed, so return doubled.The algorithm creates a new array because the required result is separate from items. It must not overwrite the supplied input.
1Algorithm doubleValues(items)
2
3Input:
4 items: an array of values
5
6Return:
7 A new array containing 2 times each value in items, in the same order
8
9Mutation behavior:
10 Does not modify items
11
12Helper contract:
13 append(array, value) adds value as one new final element of array.
14 It preserves all elements already in array and their order.
15
161. doubled ← new empty array
172. i ← 0
183. while i < length(items)
194. currentValue ← items[i]
205. append(doubled, 2 × currentValue)
216. i ← i + 1
227. return doubledThe boundary is in line 3:
1i < length(items)For an array of length 3, valid indices are 0, 1, and 2. When i becomes 3, there is no items[3] to read, so the loop stops.
Use the original input:
1items = [4, 1, 7]| Pseudocode line | State |
|---|---|
| Line 1 | doubled = [] |
| Line 2 | i = 0 |
| Pseudocode line | State change |
|---|---|
| Line 3 | 0 < length(items) is 0 < 3, so enter the loop. |
| Line 4 | currentValue = items[0] = 4 |
| Line 5 | Append 2 × 4 = 8; doubled = [8] |
| Line 6 | i = 1 |
| Pseudocode line | State change |
|---|---|
| Line 3 | 1 < 3, so enter the loop. |
| Line 4 | currentValue = items[1] = 1 |
| Line 5 | Append 2 × 1 = 2; doubled = [8, 2] |
| Line 6 | i = 2 |
| Pseudocode line | State change |
|---|---|
| Line 3 | 2 < 3, so enter the loop. |
| Line 4 | currentValue = items[2] = 7 |
| Line 5 | Append 2 × 7 = 14; doubled = [8, 2, 14] |
| Line 6 | i = 3 |
| Pseudocode line | State change |
|---|---|
| Line 3 | 3 < 3 is false, so exit the loop. |
| Line 7 | Return [8, 2, 14]. |
The original input remains unchanged:
1items = [4, 1, 7]
2doubled = [8, 2, 14]Use the invariant:
At the start of iteration
i,doubledcontains exactly 2 times each of the firstiinput items, in the same order.
Before the first iteration, line 1 creates:
1doubled = []Line 2 sets:
1i = 0There are no first 0 input items to transform. The empty array contains exactly the required transformed values for zero processed items. The invariant holds before the loop begins.
Assume the invariant holds at the start of an iteration with i < length(items).
items[i], the next unprocessed input value.2 × items[i].append keeps all earlier output values in their existing order and adds this one transformed value at the end.i by 1.At the start of the next iteration, doubled contains the doubled values for the first i + 1 input items, in the same order. The invariant is preserved.
Each iteration appends one output value for one processed input value.
The loop ends when:
1i = length(items)Let n = length(items). By the invariant, doubled then contains the doubled values for the first n input items. Those are all input items.
The algorithm returns one correctly transformed output value for every input value, in the original order, without changing items.
Let n be the length of items.
The loop runs once for each index from 0 through n - 1, so it runs n times.
In each iteration, the algorithm:
2.i.Each iteration performs a fixed amount of work. Across n iterations, the running time is:
1O(n)For an empty input, the loop runs 0 times. For every input length, the algorithm performs one iteration per input item.
Separate the categories.
| Memory category | Growth |
|---|---|
Given input items | n values, but not auxiliary space |
Scalars i and currentValue | Fixed count, so O(1) |
New output array doubled | Grows from 0 values to n values |
The output array is live while it is being built. Its largest size occurs at completion, when it holds n values. The peak size of the new collection is linear in n.
There are two reporting conventions:
Count the newly allocated output as additional storage.
doubled holds n values, so additional storage is:
1O(n)Exclude the returned output from auxiliary space.
The non-output variables are only i and currentValue, a fixed number of scalars:
1O(1) non-output auxiliary space
2O(n) output storageState the convention instead of treating input storage, output storage, and auxiliary space as interchangeable.
| Input | Returned output | Output length | Non-output scalar storage |
|---|---|---|---|
[] | [] | 0 | Fixed count |
[5] | [10] | 1 | Fixed count |
[0, -2] | [0, -4] | 2 | Fixed count |
[4, 4, 4] | [8, 8, 8] | 3 | Fixed count |
Zero values, negative values, and duplicates change the contents of doubled. Every input slot still produces one output slot.
Incorrect assumption:
1items has n cells, so this algorithm uses O(n) auxiliary space because of items.Exposing input:
1items = [4, 1, 7]Wrong classification:
The three cells of items are labeled as newly allocated workspace.
Why it is wrong:
items was given to the algorithm. Auxiliary space means memory used beyond the provided input representation.
Correction:
Report input storage separately. The new array doubled is the linear-sized allocation. If returned output is excluded by convention, the non-output auxiliary variables are O(1).
doubledIncorrect assumption:
1doubled is one variable name, so it uses O(1) space.Exposing state:
1doubled = [8, 2, 14]Wrong classification:
Only the identifier doubled is counted, while its three stored values are ignored.
Why it is wrong:
The collection has one slot for each stored element. At completion, it has n slots.
Correction:
Count the collection contents. doubled grows from length 0 to length n, so its storage is O(n).
Incorrect assumption:
1A loop runs n times, so it must use O(n) extra space.Exposing input:
1[4, 1, 7]Consider an algorithm that sums these values using one accumulator.
Wrong classification:
1O(n) extra spaceWrong state idea:
The analysis treats each new accumulator value as if all earlier accumulator values remain stored.
Why it is wrong:
One accumulator is reused:
1accumulator = 0
2accumulator = 4
3accumulator = 5
4accumulator = 12There is still only one accumulator storage location, plus a fixed number of other scalars.
Correction:
Repeatedly changing a fixed number of scalar variables uses:
1O(1) auxiliary spaceA loop can take linear time while using constant auxiliary space. Live memory determines storage growth; the number of loop iterations does not.
Implement:
1doubleValues(items)Required behavior:
2.items.The executable tests verify:
1def double_values(items):
2 doubled = [] # new array: grows to n values
3 i = 0
4 while i < len(items):
5 current_value = items[i]
6 doubled.append(2 * current_value)
7 i += 1
8 return doubled
9
10def total(items):
11 accumulator = 0 # one reused variable: O(1) auxiliary space
12 for value in items:
13 accumulator += value
14 return accumulator
15
16items = [4, 1, 7]
17print(items, "->", double_values(items))
18print([], "->", double_values([]))
19print("sum of", items, "=", total(items))1import java.util.ArrayList;
2import java.util.Arrays;
3import java.util.List;
4
5public class Main {
6 static List<Integer> doubleValues(int[] items) {
7 List<Integer> doubled = new ArrayList<>(); // new array: grows to n values
8 int i = 0;
9 while (i < items.length) {
10 int currentValue = items[i];
11 doubled.add(2 * currentValue);
12 i++;
13 }
14 return doubled;
15 }
16
17 static int total(int[] items) {
18 int accumulator = 0; // one reused variable: O(1) auxiliary space
19 for (int value : items) accumulator += value;
20 return accumulator;
21 }
22
23 public static void main(String[] args) {
24 int[] items = {4, 1, 7};
25 System.out.println(Arrays.toString(items) + " -> " + doubleValues(items));
26 System.out.println("[] -> " + doubleValues(new int[0]));
27 System.out.println("sum of " + Arrays.toString(items) + " = " + total(items));
28 }
29}1#include <iostream>
2#include <string>
3#include <vector>
4using namespace std;
5
6vector<int> doubleValues(const vector<int>& items) {
7 vector<int> doubled; // new array: grows to n values
8 size_t i = 0;
9 while (i < items.size()) {
10 int currentValue = items[i];
11 doubled.push_back(2 * currentValue);
12 i++;
13 }
14 return doubled;
15}
16
17int total(const vector<int>& items) {
18 int accumulator = 0; // one reused variable: O(1) auxiliary space
19 for (int value : items) accumulator += value;
20 return accumulator;
21}
22
23string show(const vector<int>& a) {
24 string s = "[";
25 for (size_t i = 0; i < a.size(); i++) s += (i ? ", " : "") + to_string(a[i]);
26 return s + "]";
27}
28
29int main() {
30 vector<int> items = {4, 1, 7};
31 cout << show(items) << " -> " << show(doubleValues(items)) << endl;
32 cout << show({}) << " -> " << show(doubleValues({})) << endl;
33 cout << "sum of " << show(items) << " = " << total(items) << endl;
34}1function doubleValues(items) {
2 const doubled = []; // new array: grows to n values
3 let i = 0;
4 while (i < items.length) {
5 const currentValue = items[i];
6 doubled.push(2 * currentValue);
7 i++;
8 }
9 return doubled;
10}
11
12function total(items) {
13 let accumulator = 0; // one reused variable: O(1) auxiliary space
14 for (const value of items) accumulator += value;
15 return accumulator;
16}
17
18const show = (a) => `[${a.join(', ')}]`;
19const items = [4, 1, 7];
20console.log(`${show(items)} -> ${show(doubleValues(items))}`);
21console.log(`${show([])} -> ${show(doubleValues([]))}`);
22console.log(`sum of ${show(items)} = ${total(items)}`);The memory beyond the input does not grow with n. Summing [4, 1, 7] reuses one accumulator that holds 0, then 4, then 5, then 12. That is one storage location, however many items you add.
Time counts operations; space counts memory held at one time. The loop that sums an array runs n times but uses O(1) auxiliary space, so iteration count does not decide storage.
Split memory into input, scalar variables and output. Find the largest amount held at one moment. Then state your convention for the returned output, because O(n) and O(1) are both right under different ones.
Not always. Auxiliary space excludes the input you were given. Some textbooks report total space, input included, so say which one you mean.
No. The count of iterations says nothing about memory. A loop that updates a fixed number of variables stays at O(1); only a structure that grows to n values makes the space linear.