Course contentsShow
← Computer Science
Lesson 304 of 2,8727. Introduction to Complexity AnalysisFree lesson

Space Complexity Notation

Expressing space complexity using Big-O, Big-Theta, and Big-Omega notation.

Space Complexity Notation

What you'll learn: How to express how much memory an algorithm uses with Big-O, Big-Theta, and Big-Omega notation.


The Core Idea

Just like we analyze time complexity with Big-O, Big-Theta, and Big-Omega, we use the exact same notation to describe space complexity. These tools tell us how an algorithm's memory usage grows as the input size increases.

When you analyze space, you're counting memory needs—variables, array elements, recursive call stack frames—just as you counted operations for time. The notation works identically:

  • Big-O gives an upper bound on space usage (worst-case scenario)
  • Big-Omega gives a lower bound (best-case scenario)
  • Big-Theta gives a tight bound (space grows at exactly this rate)

Examples in Plain Terms

If you create an array of size n, your space complexity is O(n)—it grows linearly with input.

If you use a fixed number of variables (say, three integers) regardless of input size, your space is O(1)—constant space.

If you make a recursive function that calls itself n times, each call adds a frame to the stack, using O(n) space.

Why Use All Three?

Just like with time complexity:

  • Use O(...) when describing the maximum memory you might need
  • Use Θ(...) when the space usage is exactly characterized
  • Use Ω(...) when describing minimum memory requirements (less common in practice)

Most often, you'll see space complexity expressed as O(...) because we care about ensuring we don't exceed memory limits.


Key Takeaway: Space complexity uses Big-O, Big-Theta, and Big-Omega notation exactly like time complexity—they describe how memory usage scales with input size.