Array initialization in C++ - Time & Space Complexity

Time Complexity: Array initialization

O(n)

Understanding Time Complexity

When we create and fill an array, the time it takes depends on how many items we add.

We want to know how the work grows as the array size grows.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

This code creates an array of 1000 integers and sets each element to zero.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Setting each array element to zero.
• How many times: Exactly 1000 times, once for each element.

How Execution Grows With Input

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

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

Pattern observation: The work grows directly in proportion to the number of elements.

Final Time Complexity

Time Complexity: O(n)

This means the time to initialize the array grows linearly with the number of elements.

Common Mistake

[X] Wrong: "Initializing an array is instant and does not depend on size."

[OK] Correct: Each element must be set, so the time grows with the number of elements.

Interview Connect

Understanding how array initialization scales helps you reason about performance in many programs.

Self-Check

"What if we initialize the array with a fixed value using a built-in function? How would the time complexity change?"