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?"

Practice

1. Which of the following correctly initializes an integer array of size 5 with all elements set to zero in C++?

easy

A. int arr[5] = {};

B. int arr[5] = {1, 2, 3, 4, 5};

C. int arr[5] = 0;

D. int arr[5];

Solution

1. Step 1: Understand array initialization with empty braces

   Using empty braces {} initializes all elements to zero by default in C++.

2. Step 2: Compare options

   int arr[5] = {}; uses {} which sets all elements to zero. int arr[5] = 0; is invalid syntax for array initialization. int arr[5] = {1, 2, 3, 4, 5}; initializes with specific values. int arr[5]; leaves elements uninitialized.

3. Final Answer:

   int arr[5] = {}; -> Option A

4. Quick Check:

   Empty braces {} zero-initialize arrays [OK]

Hint: Use empty braces {} to zero-initialize arrays quickly [OK]

Common Mistakes:

• Thinking int arr[5] = 0; initializes the array to zero
• Leaving array uninitialized expecting zeros
• Confusing initialization with assignment

2. Which of the following is the correct syntax to initialize an array of 3 doubles with values 1.1, 2.2, and 3.3 in C++?

easy

A. double arr[3] = (1.1, 2.2, 3.3);

B. double arr = {1.1, 2.2, 3.3};

C. double arr[3] = {1.1, 2.2, 3.3};

D. double arr[3] = [1.1, 2.2, 3.3];

Solution

1. Step 1: Check array declaration syntax

   Arrays require specifying size and initialization with braces {} containing values.

2. Step 2: Validate each option

   double arr[3] = {1.1, 2.2, 3.3}; correctly declares a double array of size 3 with values in braces. double arr = {1.1, 2.2, 3.3}; misses size. double arr[3] = (1.1, 2.2, 3.3); uses parentheses which is invalid. double arr[3] = [1.1, 2.2, 3.3]; uses square brackets which is invalid in C++.

3. Final Answer:

   double arr[3] = {1.1, 2.2, 3.3}; -> Option C

4. Quick Check:

   Use braces {} with size for array initialization [OK]

Hint: Always use braces {} and specify size when initializing arrays [OK]

Common Mistakes:

• Omitting array size in declaration
• Using parentheses or square brackets for initialization
• Assigning values without braces

3. What is the output of the following C++ code?

int arr[4] = {5, 10};
for(int i = 0; i < 4; i++) {
    std::cout << arr[i] << " ";
}

medium

A. 5 10 5 10

B. Compilation error

C. 5 10 garbage garbage

D. 5 10 0 0

Solution

1. Step 1: Understand partial initialization of arrays

   When fewer elements are provided than the array size, remaining elements are zero-initialized.

2. Step 2: Analyze the output loop

   arr[0] = 5, arr[1] = 10, arr[2] = 0, arr[3] = 0. Loop prints all four elements separated by spaces.

3. Final Answer:

   5 10 0 0 -> Option D

4. Quick Check:

   Partial init fills rest with zeros [OK]

Hint: Partial array init fills missing elements with zero [OK]

Common Mistakes:

• Assuming uninitialized elements have garbage values
• Expecting compilation error for partial init
• Confusing output spacing

4. Identify the error in the following C++ code snippet:

int arr[3];
arr = {1, 2, 3};

medium

A. Arrays cannot be assigned values after declaration using braces

B. Array size is missing

C. Braces should be replaced with parentheses

D. No error, code is correct

Solution

1. Step 1: Understand array assignment rules in C++

   Arrays cannot be assigned new values after declaration using brace initialization syntax.

2. Step 2: Identify correct way to assign values

   Values must be assigned element-wise or initialized at declaration. Direct assignment with braces causes error.

3. Final Answer:

   Arrays cannot be assigned values after declaration using braces -> Option A

4. Quick Check:

   Arrays only initialized at declaration with braces [OK]

Hint: You can only initialize arrays at declaration, not assign with braces later [OK]

Common Mistakes:

• Trying to assign arrays with brace syntax after declaration
• Confusing arrays with std::vector assignment
• Using parentheses instead of braces

5. You want to initialize a 2D array of size 2x3 with all elements set to 7 in C++. Which code snippet correctly achieves this?

hard

A. int arr[2][3] = {7};

B. int arr[2][3]; for(int i=0; i<2; i++) for(int j=0; j<3; j++) arr[i][j] = 7;

C. int arr[2][3] = {{7}, {7}};

D. int arr[2][3] = {{7,7,7}};

Solution

1. Step 1: Analyze initialization options

   int arr[2][3] = {{7,7,7}}; sets first row to 7,7,7 and second row to 0,0,0. int arr[2][3] = {7}; sets only first element to 7, rest zero. int arr[2][3] = {{7}, {7}}; sets first element of each row to 7, rest zero. int arr[2][3]; for(int i=0; i<2; i++) for(int j=0; j<3; j++) arr[i][j] = 7; uses loops to assign 7 to every element.

2. Step 2: Identify the best approach for uniform value

   int arr[2][3]; for(int i=0; i<2; i++) for(int j=0; j<3; j++) arr[i][j] = 7; is the most scalable and clear way to set all elements to 7 regardless of array size.

3. Final Answer:

   int arr[2][3]; for(int i=0; i<2; i++) for(int j=0; j<3; j++) arr[i][j] = 7; -> Option B

4. Quick Check:

   Use loops to fill multi-dimensional arrays uniformly [OK]

Hint: Use nested loops to fill all elements with the same value [OK]

Common Mistakes:

• Assuming partial brace init sets all elements
• Using single brace sets only first element
• Not using loops for uniform initialization