Space Complexity and Memory Usage

Space complexity measures stored data as input grows. Total storage includes the input representation, while auxiliary space usually excludes the input and counts extra working memory; always state the convention. An algorithm can finish quickly yet exceed a memory limit. We compute the same sum in two ways: streaming values without saving them, or storing a vector first.

Prerequisites: Arrays and Vectors; Time Complexity.

Build the idea

1. 1. Identify what must remain available

   If only the sum is needed, each value can be discarded after adding it. Keep one accumulator and a loop index: O(1) auxiliary storage. If later operations need arbitrary old values, retain an n-element vector, using O(n) total storage. The input stream is not an n-element in-memory array until your program explicitly creates one.

2. 2. Estimate actual bytes with care

   An n-element array of T needs approximately n*sizeof(T) bytes for elements, plus any container/allocator overhead. Common contest systems use 4-byte int and 8-byte long long or double, but the language does not fix all these sizes. A vector has bookkeeping and may allocate capacity above size. A vector of vectors has overhead per inner object; a million tiny vectors can cost much more than a million integers.

3. 3. Separate automatic and dynamic storage

   Ordinary local scalars and recursive call frames commonly use the call stack; dynamically allocated vector elements typically use heap-backed storage. The exact machine layout is implementation-specific, but practical stack limits often make a huge local array unsafe even when the overall memory allowance seems sufficient. Global arrays and dynamic storage have different lifetimes; moving data does not reduce its total bytes.

4. 4. Compare implementations on one input

   Mode 0 reads and accumulates immediately. Mode 1 allocates a vector, reads all values, then sums it. Both return 11 for [5,−2,7,1]. Mode 1 needs the saved elements even though this particular task does not benefit from them. A const-reference function can inspect that vector without copying; passing by value would temporarily add another O(n) object.

5. 5. Recognize hidden memory growth

   Recursion depth d contributes O(d) call frames, even without an explicit array. A two-dimensional n×n table grows quadratically; for n=10000, even 8 bytes per cell is about 800 million bytes before overhead. Do not confuse MB with MiB when near a limit. Input size, working buffers, recursion, container capacity and allocator overhead all matter in realistic estimates.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
int main(){
    int mode,n;
    std::cin>>mode>>n;
    long long sum=0;
    if(mode==0){
        for(int i=0;i<n;++i){
            long long x;
            std::cin>>x;
            sum+=x;
        }
    }
    else{
        std::vector<long long>values(n); // Dynamic element storage, O(n).
        for(long long&x:values){
            std::cin>>x;
        }
        for(long long x:values){
            sum+=x;
        }
    }
    std::cout<<sum<<'\n';
}

Complexity analysis

O(n) time in either mode. Mode 0 uses O(1) program working memory; mode 1 uses O(n) total/working storage because it chooses to materialize the streamed input. If the vector is considered already-provided input to a separate sum function, that function alone uses O(1) auxiliary space. State the model instead of mixing these viewpoints.

Example input and output

Read mode n, mode 0 or 1 and n in 0..10^6, then n integers with |value|≤10^9. Output the sum; both modes have identical mathematical results.

Input

1 4
5 -2 7 1

Output

11

Storing the values and adding 5−2+7+1 produces 11. Mode 0 would obtain the same result without saving the array.

Practical applications

Use streaming when past elements are never needed again; use stored arrays for sorting, random access and repeated queries. Rolling DP rows can sometimes replace a whole table, but only when dependencies permit it. Analyze memory independently of time: a faster preprocessing method may intentionally spend more space.

Check your understanding

What extra storage does a recursive depth-d computation usually require?

Put it into practice

Estimate element bytes for one million long long values on an 8-byte long-long implementation.