Common Big O Pitfall: How Nested Loops Aren't Always O(n²)

Think nested loops always result in a O(n²) time complexity? Think again!

Nested loops are often associated with a time complexity of O(n²) because the inner loop runs n times for each iteration of the outer loop. However, there are exceptions to this rule. In this post, we will explore an example to demonstrate that this isn't always the case.

Two-Pointer Technique

The function removeDuplicates uses the two pointer technique to remove duplicates from a sorted array. The writePointer keeps track of the index where the next unique element can be written. The readPointer iterates through the array, and the inner while loop moves the writePointer back if it finds duplicates.

Complexity: O(n)

While the function uses nested loops, the time complexity is O(n) because each element is visited at most twice. Its worst-case time complexity is therefore O(2n) which is simplified to O(n).

Takeaways

• Most nested loops result in O(n²) time complexity, but there are exceptions
• When analyzing a nested loop, if two pointers are used, be suspicious
• If the pointers only move forward (or backward within limits), it's likely O(n)