DSA Day 84: Cracking the Complexity Assignment

📅 Date: July 16, 2026

🧠 Mood: The Problem Solver 🛠️

🔥 Topic: DSA Day 84: Cracking the Complexity Assignment

🧩 Passing the Acid Test

Reading theory about Big O Notation is one thing, but applying it to raw code snippets is the ultimate acid test. Interviewers love to throw nested loops with weird increment conditions on the whiteboard to see if you actually understand how the math scales.

Today, I sat down and tackled the final three assignment questions for the Time & Space Complexity module. No compilers. No execution timers. Just raw static analysis. Here is the exact breakdown of the logic required to solve them.

---

1️⃣ Analyzing Nested Independent Loops

int i, j, k = 0;
for (i = n / 2; i <= n; i++) {
    for (j = 2; j <= n; j = j * 2) {
        k = k + n / 2;
    }
}

To find the Time Complexity here, we must evaluate the loops from the outside in.

• The Outer Loop: It starts at $N/2$ and increments by $1$ until it reaches $N$. The total number of iterations is $N - N/2 = N/2$. In Big O Notation, we drop the constants (the division by 2), leaving us with $O(N)$.
• The Inner Loop: It starts at $2$ and multiplies by $2$ every step (j = j * 2). Because it grows exponentially, it reaches $N$ in a logarithmic number of steps. This gives us $O(\log N)$.
• The Conclusion: Since the inner loop executes completely for every single iteration of the outer loop, we multiply them together: $O(N) \times O(\log N)$.

Correct Answer: B. $O(N \log N)$

---

2️⃣ The Logarithmic Base Trap

for(int i=0; i

This is a brilliantly tricky question. At first glance, you see i++ in the loop header and assume it is linear $O(N)$. But look at the loop body: i *= k. Let's trace the execution:

• Iteration 1: i = 0. The body makes it 0 * k = 0. Then the loop header increments it: i++ makes it $1$.
• Iteration 2: i = 1. The body makes it 1 * k = k. The loop header increments it: i++ makes it $k+1$.
• Iteration 3: i = k+1. The body makes it (k+1) * k = k^2 + k. The header increments it.

The variable i is growing by powers of $k$ ($k^1, k^2, k^3...$). The number of iterations required for $k^x$ to reach $N$ is exactly $\log_k N$. Because the growth factor is $k$, the base of the logarithm is $k$.

Correct Answer: C. $O(\log_k N)$

---

3️⃣ The "Always" Fallacy

The Statement

"Algorithm A and B have a worst-case running time of O(n) and O(logn), respectively. Therefore, algorithm B always runs faster than algorithm A."

The keyword that destroys this statement is "always".

Big O Notation represents asymptotic behavior—how the algorithm performs as the input size $N$ approaches infinity. It intentionally ignores constant factors.

Imagine Algorithm B has a massive constant overhead: $10,000 \log N$. And Algorithm A is highly optimized: $2N$. If the input size is incredibly small (e.g., $N = 2$), Algorithm A will easily execute faster than Algorithm B. $O(\log N)$ only dominates $O(N)$ when the input scales up to large numbers.

Correct Answer: B. False

---

🎯 The Final Word

Knocking out these assignments proves that the logic is finally sticking. The days of blindly guessing an algorithm's efficiency are over. Time to close the book on Time and Space Complexity and prepare for the next data structure.