Memory allocation and deallocation in C++ - Time & Space Complexity

Time Complexity: Memory allocation and deallocation

O(n)

Understanding Time Complexity

When we allocate or free memory in a program, it takes some time. Understanding how this time grows helps us write faster programs.

We want to know how the cost of memory allocation and deallocation changes as the program runs more or uses more memory.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

int* allocateArray(int n) {
    int* arr = new int[n];
    for (int i = 0; i < n; i++) {
        arr[i] = 0;
    }
    return arr;
}

void freeArray(int* arr) {
    delete[] arr;
}
    

This code allocates an array of size n, initializes it, and then frees the memory.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The for-loop that sets each element to zero.
• How many times: It runs exactly n times, once for each element.

How Execution Grows With Input

As n grows, the number of times we set elements grows the same way.

Input Size (n)	Approx. Operations
10	10 assignments
100	100 assignments
1000	1000 assignments

Pattern observation: The work grows directly with n, so doubling n doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to allocate and initialize memory grows in a straight line with the size of the array.

Common Mistake

[X] Wrong: "Memory allocation is always a constant time operation, no matter the size."

[OK] Correct: Allocating memory often involves setting up space and initializing it, which takes time proportional to the size requested.

Interview Connect

Understanding how memory operations scale helps you write efficient code and explain your choices clearly in interviews.

Self-Check

"What if we removed the loop that initializes the array? How would the time complexity change?"