Common array operations - Time & Space Complexity

Time Complexity: Common array operations

O(n)

Understanding Time Complexity

When working with arrays, it is important to know how the time to complete operations changes as the array grows.

We want to understand how fast or slow common array tasks run when the array size increases.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Find the sum of all elements in an array
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 every number in the array to find the total sum.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through each element of the array once.
• How many times: Exactly n times, where n is the array size.

How Execution Grows With Input

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

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

Pattern observation: The work grows in a straight line with the array size.

Final Time Complexity

Time Complexity: O(n)

This means the time to complete the sum grows directly in proportion to the number of elements.

Common Mistake

[X] Wrong: "Adding all elements is a constant time operation because it just adds numbers."

[OK] Correct: Even though adding two numbers is quick, you must add each element one by one, so the total time depends on how many elements there are.

Interview Connect

Understanding how array operations scale helps you explain your code choices clearly and shows you know how to handle data efficiently.

Self-Check

"What if we searched for a specific value instead of summing all elements? How would the time complexity change?"