DSA Series

Time & Space Complexity

March 2026 · 4 min read

Every algorithm has a cost — how much time it takes and how much memory it uses. Understanding, deriving, and comparing these costs is the most fundamental skill in computer science. This series covers complexity analysis from the ground up: formal definitions, mathematical derivations, proof techniques, and practical pattern recognition.

The Series

1. Introduction to Big-O

What Big-O means intuitively and formally. Why we ignore constants. How to count operations and derive complexity from code. The RAM model.

Foundations →

2. Asymptotic Notation

Big-O, Big-Ω, Big-Θ, little-o, little-ω — formal definitions with limit proofs, properties, and worked examples.

O, Ω, Θ, o, ω →

3. Common Complexities

The complexity hierarchy from O(1) to O(n!). Each class with code examples, mathematical derivations, and real-world algorithms.

Gallery & Derivations →

4. Recurrence Relations

Master Theorem, substitution method, recursion tree method. Deriving complexity of recursive algorithms from T(n) equations.

T(n) = aT(n/b) + f(n) →

5. Amortized Analysis

When worst-case per-operation is misleading. Aggregate, accounting, and potential methods. Dynamic arrays, union-find, splay trees.

Beyond Worst-Case →

6. Space Complexity

Stack frames and recursion depth. Auxiliary vs total space. In-place algorithms. The space-time trade-off. Memory hierarchy.

Memory Analysis →

7. Why Logarithms Appear

The mathematical reason O(log n) shows up everywhere: binary search, balanced trees, divide-and-conquer. Deriving log from halving.

The Halving Principle →

8. Sorting Lower Bounds

Proof that comparison-based sorting is Ω(n log n). Decision tree argument. Stirling's approximation. Where each sorting algorithm fits.

Ω(n log n) Proof →

9. Complexity Patterns

Cheat sheet: how to recognize complexity from code structure. Nested loops, recursion shapes, common interview patterns.

Interview Ready →