Algorithm Analysis and Big O Notation

Algorithm Space Complexity

What is space complexity and how does it relate to time complexity?

Abstract art representing computer programming

Space complexity refers to the amount of memory space required by an algorithm, including the space of input values, for its execution. Just like time complexity, we use Big O notation to express space complexity.

Here's how space complexity relates to time complexity:


Often, there is a trade-off between time and space complexity. We can often reduce time complexity by using more memory, and vice versa. For example:

int fibonacci(int n) {
  if (n <= 1) return n;
  return fibonacci(n-1) + fibonacci(n-2);

This recursive Fibonacci function has O(2n)O(2^n) time complexity but O(n)O(n) space complexity due to the recursive call stack.

We can optimize time complexity to O(n)O(n) by using an array to store results, but this increases space complexity to O(n)O(n):

int fibonacci(int n) {
  if (n <= 1) return n;
  int fib[n+1];
  fib[0] = 0; fib[1] = 1;
  for (int i = 2; i <= n; i++) {
    fib[i] = fib[i-1] + fib[i-2];
  return fib[n];

Auxiliary Space

Space complexity includes both the space of input values and the auxiliary space used by the algorithm. Auxiliary space refers to the extra space or temporary space used by an algorithm, not including the space used for input values.


In many cases, time complexity is more critical than space complexity because memory is often less costly than computational time. However, for systems with limited memory or very large datasets, space complexity can be a major constraint.

Big O Notation

Just like time complexity, we drop constants and lower order terms for space complexity. For example, an algorithm that uses a single integer and an array of size n would be considered to have O(n)O(n) space complexity.

When designing algorithms, it's important to consider both time and space complexity and choose the appropriate trade-off for your specific problem and constraints.

Answers to questions are automatically generated and may not have been reviewed.

A computer programmer
Part of the course:

Professional C++

Comprehensive course covering advanced concepts, and how to use them on large-scale projects.

Free, unlimited access

This course includes:

  • 124 Lessons
  • 550+ Code Samples
  • 96% Positive Reviews
  • Regularly Updated
  • Help and FAQ
Free, Unlimited Access

Professional C++

Comprehensive course covering advanced concepts, and how to use them on large-scale projects.

Screenshot from Warhammer: Total War
Screenshot from Tomb Raider
Screenshot from Jedi: Fallen Order
Contact|Privacy Policy|Terms of Use
Copyright © 2024 - All Rights Reserved