Traversal Forward and Backward in DSA C - Time & Space Complexity

Time Complexity: Traversal Forward and Backward

O(n)

Understanding Time Complexity

We want to understand how long it takes to move through a list from start to end and then back from end to start.

How does the time needed change as the list gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

void traverseForwardBackward(int arr[], int n) {
    // Traverse forward
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    // Traverse backward
    for (int i = n - 1; i >= 0; i--) {
        printf("%d ", arr[i]);
    }
}
    

This code prints all elements of an array first from the start to the end, then from the end back to the start.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Two separate loops that each visit every element once.
• How many times: Each loop runs exactly n times, where n is the number of elements.

How Execution Grows With Input

As the list size grows, the total steps grow roughly twice as fast because we go forward and backward.

Input Size (n)	Approx. Operations
10	20 (10 forward + 10 backward)
100	200 (100 forward + 100 backward)
1000	2000 (1000 forward + 1000 backward)

Pattern observation: The total steps double as input size doubles, showing a linear growth pattern.

Final Time Complexity

Time Complexity: O(n)

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

Common Mistake

[X] Wrong: "Because there are two loops, the time complexity is O(n²)."

[OK] Correct: The loops run one after another, not nested. So their times add up, not multiply.

Interview Connect

Understanding how simple traversals add up helps you explain and optimize code clearly in interviews.

Self-Check

"What if we combined the forward and backward traversals into a single loop that prints both directions simultaneously? How would the time complexity change?"