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

Time Complexity: Traversal Forward and Backward

O(n)

Understanding Time Complexity

When we move through a list or collection from start to end and then back again, we want to know how long it takes. This helps us understand how the work grows as the list gets bigger.

We ask: How does the time to go forward and backward change with the size of the list?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

def traverse_forward_backward(arr):
    # Traverse forward
    for i in range(len(arr)):
        print(arr[i])
    # Traverse backward
    for i in range(len(arr) - 1, -1, -1):
        print(arr[i])

This code goes through the list from the first item to the last, then from the last item back to the first.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Two separate loops each visiting every item once.
• How many times: Each loop runs exactly n times, where n is the list size.

How Execution Grows With Input

As the list grows, the total steps grow roughly twice as much 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 grow linearly with the list size, doubling because of two passes.

Final Time Complexity

Time Complexity: O(n)

This means the time to complete the forward and backward traversal grows in a straight line with the size of the list.

Common Mistake

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

[OK] Correct: The loops run one after another, not inside each other, so their times add up, not multiply.

Interview Connect

Understanding how multiple passes over data add up helps you explain your code clearly and shows you know how to judge efficiency in real tasks.

Self-Check

"What if we combined the forward and backward traversal into a single loop that prints two items per step? How would the time complexity change?"