One-dimensional arrays in C++ - Time & Space Complexity

Time Complexity: One-dimensional arrays

O(n)

Understanding Time Complexity

When working with one-dimensional arrays, it's important to understand how the time to process them grows as the array gets bigger.

We want to know how the number of steps changes when the array size increases.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

This code adds up all the numbers in a one-dimensional array of size n.

Identify Repeating Operations

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

How Execution Grows With Input

As the array gets bigger, the number of additions grows in a straight line with the size.

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

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

Final Time Complexity

Time Complexity: O(n)

This means the time to sum the array grows directly with the number of elements.

Common Mistake

[X] Wrong: "The loop runs faster because it just adds numbers, so time doesn't grow much with size."

[OK] Correct: Even simple steps add up; more elements mean more additions, so time grows with n.

Interview Connect

Understanding how loops over arrays scale is a key skill that helps you reason about many real-world problems and algorithms.

Self-Check

"What if we nested another loop inside to compare each element with every other element? How would the time complexity change?"