Array traversal in C - Time & Space Complexity

Time Complexity: Array traversal

O(n)

Understanding Time Complexity

When we look at array traversal, we want to know how the time to run the code changes as the array gets bigger.

We ask: How many steps does it take to visit every item in the array?

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++) {
        printf("%d\n", arr[i]);
    }
}
    

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

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The for-loop that visits each array element.
• How many times: Exactly once for each element, so n times.

How Execution Grows With Input

As the array size grows, the number of steps grows the same way.

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

Pattern observation: The steps increase directly with the number of items. Double the items, double the steps.

Final Time Complexity

Time Complexity: O(n)

This means the time to run grows in a straight line with the size of the array.

Common Mistake

[X] Wrong: "Visiting each element takes the same time no matter how big the array is."

[OK] Correct: Actually, the total time grows because you do more steps as the array gets bigger, even if each step is quick.

Interview Connect

Understanding how array traversal time grows helps you explain and write efficient code in real projects and interviews.

Self-Check

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