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

Time Complexity: Why Two Pointer Technique Beats Brute Force

O(n)

Understanding Time Complexity

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

How does the number of steps change when we use two pointers instead of brute force?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Two pointer approach to find if two numbers sum to target
int twoPointerSum(int arr[], int n, int target) {
    int left = 0, right = n - 1;
    while (left < right) {
        int sum = arr[left] + arr[right];
        if (sum == target) return 1;
        else if (sum < target) left++;
        else right--;
    }
    return 0;
}
    

This code checks pairs from both ends moving inward to find a target sum.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The while loop that moves two 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 array size grows, the two pointers move inward, checking pairs without repeating.

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

Pattern observation: The steps grow roughly in a straight line with input size.

Final Time Complexity

Time Complexity: O(n)

This means the steps increase directly with the size of the input array.

Common Mistake

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

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

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 array was not sorted? How would that affect the time complexity of the two pointer approach?"