DSA Day 80: Breaking the Hiatus & Recursion Time Complexity

📅 Date: July 11, 2026

🧠 Mood: The Comeback 🔄

🔥 Topic: DSA Day 80: Breaking the Hiatus & Recursion Time Complexity

🔋 Rebooting the System

There is no point in sugar-coating it: I haven't written a line of code in the last 10 days. Between the daily commute, college burnout, and sheer mental exhaustion from the first half of this module, I needed a hard reset. But consistency isn't about never falling off; it's about getting back on. Today, we return to the grind with Time & Space Complexity (Part 2).

Analyzing standard for loops is easy. But how do you calculate the time complexity of a function that calls itself? Recursion Time Complexity is notorious for confusing junior developers because you can't just count the loops. You have to map the call stack.

---

🔄 The Linear Recursion Trap

We started with two classic algorithmic problems: Recursive Sum of N Numbers and Recursive Factorial of N. Both of these follow the exact same execution pattern.

Calculating the Call Stack

To find the time complexity of a recursive function, you use a simple formula:

Total Time = (Number of Recursive Calls) $\times$ (Time taken per call)

In a factorial function (e.g., $5! = 5 \times 4!$), calculating the multiplication takes $O(1)$ constant time. But to get from $N$ down to the base case of $1$, the function must push exactly $N$ frames onto the call stack. Therefore, the time complexity is strictly $O(N)$. Furthermore, because it holds $N$ frames in memory simultaneously, its Space Complexity is also $O(N)$.