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