new operator in C++ - Time & Space Complexity

Time Complexity: new operator

O(n)

Understanding Time Complexity

When we use the new operator in C++, it creates space in memory for data. Understanding how long this takes helps us write faster programs.

We want to know: How does the time to create new memory grow as we ask for more?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

This code creates an array of size n using new and then fills it with values.

Identify Repeating Operations

Look at what repeats in this code.

• Primary operation: The loop that sets each array element.
• How many times: Exactly n times, once for each element.

How Execution Grows With Input

As n grows, the number of steps to fill the array grows the same way.

Input Size (n)	Approx. Operations
10	About 10 steps to fill
100	About 100 steps to fill
1000	About 1000 steps to fill

Pattern observation: The work grows directly with the size of the array.

Final Time Complexity

Time Complexity: O(n)

This means the time to fill the array grows in a straight line with the number of elements.

Common Mistake

[X] Wrong: "Using new to create an array is instant and does not depend on size."

[OK] Correct: While new allocates memory quickly, filling or initializing each element takes time proportional to the number of elements.

Interview Connect

Knowing how memory allocation and initialization scale helps you explain program speed clearly and shows you understand how computers handle data.

Self-Check

"What if we replaced the loop with a function that copies values from another array? How would the time complexity change?"