SahilLog

📅 Date: July 17, 2026

🧠 Mood: The Finisher 🏁

🔥 Topic: DSA Day 85: The Final Complexity Bosses

🛡️ Closing the Chapter

Due to a slight shift in my schedule, today marks Day 85 of the grind. This is it. The absolute final two questions of the Time & Space Complexity assignment. If you can analyze these without getting tricked by the loop conditions, you are officially ready to move on to advanced Data Structures.

No more theory. Let's break down the brutal truth of how these two specific algorithms scale in a production environment.

1️⃣ The Square Root Trap

int floorSqrt(int x) {
    if (x == 0 || x == 1) return x;
    int i = 1, result = 1;
    
    while (result <= x) {
        i++;
        result = i * i;
    }
    return i - 1;
}

At first glance, a while loop makes you think of $O(N)$ or maybe $O(\log N)$ if it's dividing. But look closely at the updating condition: result = i * i.

The Execution: The loop continues as long as result <= x, which is mathematically identical to $i^2 \le x$.
The Math: If we solve for $i$, the loop terminates the moment $i > \sqrt{x}$. Therefore, the total number of iterations the loop will perform is exactly proportional to the square root of $x$.
Time Complexity: $O(\sqrt{x})$ (or $O(\sqrt{N})$). This is a massive optimization over $O(N)$. If $x = 1,000,000$, a linear loop takes a million steps, but this loop finishes in just $1,000$ steps.
Space Complexity: $O(1)$ Constant Space. We only declare two basic integer variables (i and result). No extra arrays or data structures are created regardless of how large $x$ gets.

2️⃣ The Dependent Inner Loop

int a = 0;
for (int i = 0; i < n; ++i) {
    for (int j = n; j > i; --j) {
        a = a + i + j;
    }
}

This is a classic variation of the $O(N^2)$ trap. The inner loop's termination condition depends directly on the outer loop's variable (j > i). Let's map the iterations:

When i = 0, the inner loop runs from $n$ down to $1$ ($n$ times).
When i = 1, the inner loop runs from $n$ down to $2$ ($n - 1$ times).
When i = n - 1, the inner loop runs from $n$ down to $n$ ($1$ time).

The Final Calculation

The total number of operations is the sum: $n + (n-1) + (n-2) + \dots + 1$.

Mathematically, this evaluates to $\frac{n(n+1)}{2}$, which expands to $\frac{n^2}{2} + \frac{n}{2}$. As always, we drop the constants and the lower-order terms.

Time Complexity: $O(N^2)$ Quadratic Time.
Space Complexity: $O(1)$ Constant Space (only integer trackers are used).

🎯 Module Complete

That is it. The Time and Space Complexity module is 100% finished. No more theory, no more abstract math. It is time to get back to writing raw, optimized algorithms.