DSA Day 78: Nested Loops & Quadratic Traps

📅 Date: June 30, 2026

🧠 Mood: The Debugger 🐞

🔥 Topic: DSA Day 78: Nested Loops & Quadratic Traps

🔍 Theory Meets Execution

The theory is over. Today was entirely dedicated to analyzing actual code blocks. The curriculum provided three brutal practice sets specifically designed to trick you into calculating the wrong time complexity.

A standard for loop traversing an array is $O(N)$. That is basic. But the true test of a developer is analyzing nested loops, particularly when looking at classic algorithms like Bubble Sort.

---

⚠️ The $O(N^2)$ Trap

In Bubble Sort, you have an outer loop running $N$ times, and an inner loop running $N - i$ times.

Mathematical Breakdown

The total number of operations isn't exactly $N \times N$. It is mathematically the sum of the first $N$ natural numbers: $\frac{N(N-1)}{2}$.

If we expand this, we get $\frac{N^2}{2} - \frac{N}{2}$. Applying the rules of Big O Notation from Day 1, we drop the constants (the division by 2) and drop the lower-order term ($N$). The final, absolute worst-case time complexity is $O(N^2)$.

Quadratic time complexity is a performance killer. If an input size grows from 1,000 to 10,000, an $O(N)$ algorithm takes 10 times longer. An $O(N^2)$ algorithm takes 100 times longer. Recognizing this trap in your code is the first step toward optimizing it.