Array traversal in C++ - Time & Space Complexity

Time Complexity: Array traversal

O(n)

Understanding Time Complexity

When we go through each item in an array one by one, we want to know how the time it takes grows as the array gets bigger.

We ask: How does the work increase when the array size increases?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;
}
    

This code goes through each element of the array and prints it out once.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Accessing and printing each element of the array.
• How many times: Exactly once for each of the n elements in the array.

How Execution Grows With Input

As the array gets bigger, the number of steps grows directly with the number of elements.

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

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

Final Time Complexity

Time Complexity: O(n)

This means the time to finish grows in a straight line with the number of items in the array.

Common Mistake

[X] Wrong: "Since the loop is simple, it must be constant time O(1)."

[OK] Correct: Even a simple loop that touches every element depends on how many elements there are, so time grows with n, not fixed.

Interview Connect

Understanding how simple loops scale helps you explain and improve code efficiency in many real tasks.

Self-Check

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