Array Declaration and Initialization in DSA C++ - Time & Space Complexity

Time Complexity: Array Declaration and Initialization

O(n)

Understanding Time Complexity

We want to understand how the time needed to create and fill an array changes as the array size grows.

How does the work increase when we make bigger arrays?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

This code creates an array of size n and sets each element to zero.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

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

How Execution Grows With Input

As the array size n grows, the number of steps to initialize grows in the same way.

Input Size (n)	Approx. Operations
10	10 steps to set elements
100	100 steps to set elements
1000	1000 steps to set elements

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

Final Time Complexity

Time Complexity: O(n)

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

Common Mistake

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

[OK] Correct: Each element must be set individually, so bigger arrays take more time.

Interview Connect

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

Self-Check

"What if we declared the array but did not initialize elements in a loop? How would the time complexity change?"

Practice

1. Which of the following is the correct way to declare an integer array of size 5 in C++?

easy

A. int arr = new int[5];

B. array<int> arr(5);

C. int arr[5];

D. int arr();

Solution

1. Step 1: Understand basic array declaration syntax

   In C++, to declare a fixed-size array, we use the syntax type name[size];.

2. Step 2: Check each option

   int arr[5]; uses int arr[5]; which is the correct syntax for declaring an integer array of size 5. int arr = new int[5]; uses dynamic allocation syntax which is valid but not a declaration. array<int> arr(5); uses a non-standard syntax. int arr(); declares a function, not an array.

3. Final Answer:

   int arr[5]; -> Option C

4. Quick Check:

   Array declaration = int arr[5]; [OK]

Hint: Use type name[size]; for fixed-size arrays [OK]

Common Mistakes:

• Using parentheses instead of square brackets
• Confusing dynamic allocation with declaration
• Using non-standard syntax

2. Which of the following is the correct syntax to initialize an array of 3 integers with values 1, 2, and 3 in C++?

easy

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

B. int arr = {1, 2, 3};

C. int arr[3] = (1, 2, 3);

D. int arr[3] = [1, 2, 3];

Solution

1. Step 1: Recall array initialization syntax

   In C++, arrays are initialized using curly braces with values separated by commas, like int arr[size] = {values};.

2. Step 2: Evaluate each option

   int arr[3] = {1, 2, 3}; correctly uses curly braces with values. int arr = {1, 2, 3}; misses the size in declaration. int arr[3] = (1, 2, 3); uses parentheses which is invalid. int arr[3] = [1, 2, 3]; uses square brackets which is incorrect for initialization.

3. Final Answer:

   int arr[3] = {1, 2, 3}; -> Option A

4. Quick Check:

   Array init uses curly braces = int arr[3] = {1, 2, 3}; [OK]

Hint: Initialize arrays with curly braces and commas [OK]

Common Mistakes:

• Omitting array size in declaration
• Using parentheses or square brackets for initialization
• Missing commas between values

3. What will be the output of the following C++ code?

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

medium

A. 10 20 0 20

B. 10 20 0 0

C. 10 20 10 20

D. 10 20 garbage garbage

Solution

1. Step 1: Understand partial array initialization

   When an array is partially initialized, the remaining elements are set to zero automatically in C++.

2. Step 2: Trace the loop output

   The first two elements are 10 and 20 as given. The last two elements are 0 by default. So the output prints: 10 20 0 0

3. Final Answer:

   10 20 0 0 -> Option B

4. Quick Check:

   Partial init fills rest with 0 = 10 20 0 0 [OK]

Hint: Uninitialized array elements default to 0 if partially initialized [OK]

Common Mistakes:

• Assuming uninitialized elements have garbage values
• Confusing partial initialization with full initialization
• Misreading loop bounds

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

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

medium

A. Array size must be specified during declaration

B. Array elements must be initialized with parentheses

C. Missing semicolon after array declaration

D. Cannot assign values to array after declaration like this

Solution

1. Step 1: Check array declaration rules

   In C++, arrays must have size specified or be initialized at declaration. Here, int arr[]; is invalid because size or initializer is missing.

2. Step 2: Understand assignment to arrays

   Arrays cannot be assigned values after declaration using = { ... }. This syntax is invalid. Initialization must happen at declaration.

3. Final Answer:

   Cannot assign values to array after declaration like this -> Option D

4. Quick Check:

   Arrays can't be assigned with braces after declaration [OK]

Hint: Initialize arrays only at declaration, no later assignment [OK]

Common Mistakes:

• Trying to assign array values after declaration
• Omitting array size without initializer
• Confusing array assignment with pointer assignment

5. You want to declare and initialize a 2D integer array with 2 rows and 3 columns, where all elements are zero. Which is the best way to do this in C++?

hard

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

B. int arr[2][3] = {{0,0,0},{0,0,0}};

C. int arr[2][3]; memset(arr, 0, sizeof(arr));

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

Solution

1. Step 1: Understand zero initialization of multi-dimensional arrays

   In C++, initializing the first element to zero with {0} sets all elements to zero by default.

2. Step 2: Compare options for simplicity and correctness

   int arr[2][3] = {0}; uses {0} which zero-initializes all elements. int arr[2][3] = {{0,0,0},{0,0,0}}; explicitly lists zeros but is longer. int arr[2][3]; memset(arr, 0, sizeof(arr)); uses memset which works but is less clean. int arr[2][3] = {0, 0, 0, 0, 0, 0}; lists all zeros but is verbose.

3. Final Answer:

   int arr[2][3] = {0}; -> Option A

4. Quick Check:

   Use {0} to zero initialize entire array [OK]

Hint: Use {0} to zero initialize all elements in arrays [OK]

Common Mistakes:

• Not knowing {0} zero initializes entire array
• Using memset without including <cstring>
• Writing verbose initializers unnecessarily