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