Array Traversal Patterns in DSA C - Time & Space Complexity

Time Complexity: Array Traversal Patterns

O(n)

Understanding Time Complexity

When we go through an array to check or change its items, we want to know how long it takes as the array grows.

We ask: How does the work increase when the array gets bigger?

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

This code goes through each item in the array once and prints it.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

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

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: Doubling the array size doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to finish grows directly 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: The loop runs once for each item, so time grows with array size, not fixed.

Interview Connect

Understanding how simple loops scale helps you explain your code clearly and shows you know how programs behave with bigger data.

Self-Check

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