DSA Day 77: Space Complexity & Alternate Notations

📅 Date: June 29, 2026

🧠 Mood: The Optimizer ⚙️

🔥 Topic: DSA Day 77: Space Complexity & Alternate Notations

💾 Real Estate in RAM

During my commute from Thane to Kandivali for college lectures, I usually review the notes from the previous day. Big O Notation for time execution made sense. But today, the curriculum shifted from processor ticks to RAM allocation. We tackled Space Complexity.

Time is money, but memory is real estate. Space complexity measures the total amount of extra memory an algorithm requires to run as a function of the input size.

---

📐 Beyond the Worst Case

While Big O is the industry standard for worst-case scenarios, the curriculum introduced two other asymptotic notations that interviewers sometimes use to test your deep understanding:

• Omega Notation (Ω): This represents the Best Case scenario. If you are searching an array for a number and find it on the very first try, that is $\Omega(1)$. It's good to know, but rarely useful for guaranteeing system stability.
• Theta Notation (Θ): This represents the Average Case or tight bound. It means the algorithm scales at this exact rate from both the upper and lower bounds.

The Auxiliary Space Trap

When calculating Space Complexity, you do not count the memory taken by the input array itself. You only count the extra memory (Auxiliary Space) your code creates. If you pass an array of size $N$ into a function, and your function creates a single integer variable to keep track of a sum, your space complexity is $O(1)$ constant time. If your function duplicates the array, it becomes $O(N)$ linear space.