Why Two Pointer Technique Beats Brute Force in DSA Python - Performance Analysis

Time Complexity: Why Two Pointer Technique Beats Brute Force

O(n)

Understanding Time Complexity

We want to see why using two pointers is faster than checking every pair one by one.

How does the number of steps change when input grows?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

def two_sum_sorted(arr, target):
    left, right = 0, len(arr) - 1
    while left < right:
        current_sum = arr[left] + arr[right]
        if current_sum == target:
            return True
        elif current_sum < target:
            left += 1
        else:
            right -= 1
    return False

This code checks if two numbers in a sorted list add up to a target using two pointers.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The while loop moves pointers through the array.
• How many times: At most, each pointer moves across the array once, so up to n steps total.

How Execution Grows With Input

As the list gets bigger, the steps grow roughly in a straight line with the size.

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

Pattern observation: The steps increase directly with input size, not faster.

Final Time Complexity

Time Complexity: O(n)

This means the time to finish grows in a straight line as the list gets bigger.

Common Mistake

[X] Wrong: "Two pointers still check every pair, so it's as slow as brute force."

[OK] Correct: Two pointers smartly skip many pairs by moving inward, so they do fewer checks than brute force.

Interview Connect

Knowing why two pointers are faster helps you explain your choices clearly and shows you understand efficient problem solving.

Self-Check

"What if the input array was not sorted? How would the time complexity change if we still tried two pointers?"