Array size and bounds in C - Time & Space Complexity

Time Complexity: Array size and bounds

O(1)

Understanding Time Complexity

When working with arrays, it is important to understand how the size of the array affects the time it takes to access or process its elements.

We want to know how the number of operations changes as the array size grows.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

#include <stdio.h>

int main() {
    int arr[100];
    int sum = 0;
    for (int i = 0; i < 100; i++) {
        sum += arr[i];
    }
    printf("Sum: %d\n", sum);
    return 0;
}
    

This code sums all elements in an array of fixed size 100.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Accessing each element of the array once to add it to sum.
• How many times: Exactly 100 times, once per element.

How Execution Grows With Input

Since the array size is fixed at 100, the number of operations stays the same no matter what.

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

Pattern observation: The operations do not grow with input size because the array size is fixed.

Final Time Complexity

Time Complexity: O(1)

This means the time to run the code does not change as input size changes because the array size is fixed.

Common Mistake

[X] Wrong: "Since there is a loop, the time must grow with input size."

[OK] Correct: Here, the loop runs a fixed number of times (100), so time does not grow with input size.

Interview Connect

Understanding fixed-size arrays helps you explain how code behaves when input size is constant versus variable, a key skill in interviews.

Self-Check

"What if the array size was a variable n instead of fixed 100? 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. 0 to 9

B. 1 to 10

C. 0 to 10

D. 1 to 9

Solution

1. Step 1: Understand array size declaration

   The array arr is declared with size 10, meaning it has 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 A

4. Quick Check:

   Array indexes = 0 to size-1 = 0 to 9 [OK]

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

Common Mistakes:

• Assuming array indexes start at 1
• Using size as the last index
• Confusing size with maximum 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: Recall C 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 correct syntax. Options A and C use parentheses or braces which are invalid for arrays. int arr = 5; assigns an int, not an array.

3. Final Answer:

   int arr[5]; -> Option B

4. Quick Check:

   Array declaration uses square brackets [OK]

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

Common Mistakes:

• Using parentheses instead of brackets
• Using braces instead of brackets
• Assigning a single value instead of declaring array

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

int arr[3] = {10, 20, 30};
printf("%d", arr[3]);

medium

A. Undefined behavior (may print garbage or crash)

B. 0

C. Compilation error

D. 30

Solution

1. Step 1: Analyze array size and indexing

   The array arr has size 3, valid indexes are 0, 1, 2. Accessing arr[3] 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 value, cause crash, or unpredictable output.

3. Final Answer:

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

4. Quick Check:

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

Hint: Accessing index >= size causes undefined behavior [OK]

Common Mistakes:

• Assuming arr[3] prints 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];
for(int i = 0; i <= 4; i++) {
    arr[i] = i * 2;
}

medium

A. Initialization of i is incorrect

B. Array size should be 5 instead of 4

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

D. Multiplication by 2 is invalid

Solution

1. Step 1: Check loop bounds against array size

   The array size is 4, so valid indexes are 0 to 3. The loop runs while i <= 4, which includes i=4, an invalid index.

2. Step 2: Correct the loop condition

   Changing the loop condition to i < 4 ensures indexes 0 to 3 are used, avoiding out-of-bounds access.

3. Final Answer:

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

4. Quick Check:

   Loop index must be less than array size [OK]

Hint: Use < not <= for loop index to avoid out-of-bounds [OK]

Common Mistakes:

• Using <= instead of < in loop condition
• Assuming array size includes index equal to size
• Ignoring off-by-one errors

5. Given the array declaration int nums[5] = {1, 2, 3, 4, 5};, which code snippet correctly sums all elements without causing out-of-bounds errors?

hard

A. for(int i = 0; i < 6; i++) sum += nums[i];

B. for(int i = 1; i < 5; i++) sum += nums[i];

C. for(int i = 0; i <= 5; i++) sum += nums[i];

D. for(int i = 0; i < 5; i++) sum += nums[i];

Solution

1. Step 1: Understand array size and valid indexes

   The array nums has size 5, so valid indexes are 0 to 4.

2. Step 2: Evaluate each loop condition

   for(int i = 0; i <= 5; i++) sum += nums[i]; uses i <= 5, which accesses nums[5] (out-of-bounds). for(int i = 1; i < 5; i++) sum += nums[i]; starts at 1, missing nums[0]. for(int i = 0; i < 5; i++) sum += nums[i]; uses i < 5, correctly iterating 0 to 4. for(int i = 0; i < 6; i++) sum += nums[i]; uses i < 6, accessing nums[5] (out-of-bounds).

3. Final Answer:

   for(int i = 0; i < 5; i++) sum += nums[i]; -> Option D

4. Quick Check:

   Loop from 0 to size-1 to avoid errors [OK]

Hint: Loop from 0 to less than array size for safe access [OK]

Common Mistakes:

• Using <= size causing out-of-bounds
• Starting loop at 1 missing first element
• Looping beyond array size