Array size and bounds in C++ - Time & Space Complexity

Time Complexity: Array size and bounds

O(n)

Understanding Time Complexity

When working with arrays, knowing how the size affects operations is important.

We want to see how the number of steps changes as the array gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

int sumArray(int arr[], int size) {
    int sum = 0;
    for (int i = 0; i < size; i++) {
        sum += arr[i];
    }
    return sum;
}
    

This code adds up all the numbers in an array of given size.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Adding each element of the array to sum.
• How many times: Exactly once for each element, so 'size' times.

How Execution Grows With Input

As the array gets bigger, the number of additions grows directly with its size.

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

Pattern observation: Doubling the array size doubles the work done.

Final Time Complexity

Time Complexity: O(n)

This means the time to complete grows in a straight line with the array size.

Common Mistake

[X] Wrong: "Accessing any element in the array takes longer if the array is bigger."

[OK] Correct: Accessing an element by index is always fast and does not depend on array size; only looping through all elements takes longer as size grows.

Interview Connect

Understanding how array size affects loops is a key skill that helps you write efficient code and explain your reasoning clearly.

Self-Check

"What if we only summed half the array? How would the time complexity change?"

Practice

1. What is the valid range of indexes for an array declared as int arr[10]; in C++?

easy

A. 1 to 9

B. 1 to 10

C. 0 to 10

D. 0 to 9

Solution

1. Step 1: Understand array size declaration

   The array arr is declared with size 10, meaning it holds 10 elements.

2. Step 2: Determine valid index range

   In C++, array indexing starts at 0, so valid indexes are from 0 up to size-1, which is 9.

3. Final Answer:

   0 to 9 -> Option D

4. Quick Check:

   Array size 10 means indexes 0 to 9 [OK]

Hint: Array indexes start at 0 and end at size minus 1 [OK]

Common Mistakes:

• Thinking indexes start at 1
• Including size as a valid index
• Confusing size with last index

2. Which of the following is the correct way to declare an array of 5 integers in C++?

easy

A. int arr[5];

B. int arr = 5;

C. int arr(5);

D. int arr{5};

Solution

1. Step 1: Review array declaration syntax

   In C++, arrays are declared using square brackets with the size inside, like int arr[5];.

2. Step 2: Check each option

   int arr(5); uses parentheses which is invalid for arrays. int arr = 5; assigns an int, not an array. int arr{5}; uses brace initialization but without specifying size properly.

3. Final Answer:

   int arr[5]; -> Option A

4. Quick Check:

   Array declaration uses square brackets [OK]

Hint: Use square brackets [] to declare array size [OK]

Common Mistakes:

• Using parentheses instead of brackets
• Assigning a single int instead of array
• Confusing brace initialization with size

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

int arr[3] = {10, 20, 30};
std::cout << arr[3] << std::endl;

medium

A. Undefined behavior (may print garbage or crash)

B. 0

C. 30

D. Compilation error

Solution

1. Step 1: Identify array size and index used

   The array has size 3, valid indexes are 0, 1, 2. The code accesses arr[3], which is out of bounds.

2. Step 2: Understand consequences of out-of-bounds access

   Accessing outside array bounds in C++ causes undefined behavior. It may print garbage, crash, or behave unpredictably.

3. Final Answer:

   Undefined behavior (may print garbage or crash) -> Option A

4. Quick Check:

   Out-of-bounds access causes undefined behavior [OK]

Hint: Access only indexes 0 to size-1 to avoid undefined behavior [OK]

Common Mistakes:

• Assuming arr[3] returns last element
• Expecting zero instead of garbage
• Thinking compiler catches out-of-bounds

4. Identify the error in the following code snippet:

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

medium

A. Array size should be 5

B. Initialization of array is incorrect

C. Loop condition should be i < 4, not i <= 4

D. No error, code runs fine

Solution

1. Step 1: Analyze loop bounds

   The loop runs from i = 0 to i = 4 inclusive, so it tries to access arr[4].

2. Step 2: Check array size and valid indexes

   Array size is 4, valid indexes are 0 to 3. Accessing arr[4] is out of bounds and causes undefined behavior.

3. Final Answer:

   Loop condition should be i < 4, not i <= 4 -> Option C

4. Quick Check:

   Loop must use i < size to avoid out-of-bounds [OK]

Hint: Use < size, not <= size, in loops over arrays [OK]

Common Mistakes:

• Using <= instead of < in loop condition
• Increasing array size unnecessarily
• Ignoring out-of-bounds access

5. You want to create a function that sums all elements of an integer array passed along with its size. Which of the following function signatures correctly allows safe access to the array elements without causing out-of-bounds errors?

hard

A. int sumArray(int arr[10]);

B. int sumArray(int arr[], int size);

C. int sumArray(int* arr);

D. int sumArray(int arr[]);

Solution

1. Step 1: Understand function parameter requirements

   To safely access array elements, the function must know the array size to avoid out-of-bounds access.

2. Step 2: Evaluate each signature

   int sumArray(int arr[], int size); passes both array and size, allowing safe iteration. int sumArray(int arr[10]); fixes size to 10, which is unsafe if actual size differs. int sumArray(int* arr); passes pointer without size, unsafe. int sumArray(int arr[]); passes array without size, unsafe.

3. Final Answer:

   int sumArray(int arr[], int size); -> Option B

4. Quick Check:

   Pass array and size to avoid out-of-bounds [OK]

Hint: Always pass array size with array to functions [OK]

Common Mistakes:

• Assuming fixed size in function parameter
• Not passing size leads to unsafe access
• Using pointer without size information