Skip to main content

Explore your training options in 10 minutes

Big O Notation, Part Two: Space Complexity

Christina Kopecky - December 29, 2020

Note : If you haven’t read our article on time complexity , it’s recommended to start there. Part two of this series assumes you are familiar with different possible Big O values.

In our first article about Big O Notation and time complexity , we talk about how much time it takes for the algorithm to complete when its input increases. This is important when we interact with very large datasets. A large dataset combined with a decent time complexity leads to more efficient algorithms. However, there is one more aspect to Big O Notation that needs to be considered: space complexity.

What is Space Complexity?

Time complexity and space complexity are similar as they relate to the amount of input an algorithm has. Where time complexity is related to the amount of operations an algorithm needs to perform to terminate, space complexity is related to the total amount of space needed to complete the algorithm. Space complexity is expressed in terms of Big O Notation.

Get offers and scholarships from top coding schools illustration

Find Your Bootcamp Match

  • Career Karma matches you with top tech bootcamps
  • Access exclusive scholarships and prep courses

By continuing you agree to our Terms of Service and Privacy Policy , and you consent to receive offers and opportunities from Career Karma by telephone, text message, and email.

The space complexity includes the amount of space needed for the input as well as the auxiliary space needed in the algorithm to execute. Auxiliary space is the extra space used to store temporary data structures or variables used to solve the algorithm. Just like in time complexity, the Big O of an algorithm considers the worst case scenario, or the asymptotic upper bound.

Figuring Out the Space Required to Run an Algorithm

When we figure out the space complexity of an algorithm, take a look at two things: the input size and the auxiliary space needed to run the function. In most cases, we don’t reduce the size down to how many bytes the input is – we just look at the amount of memory the input or auxiliary space needs to use.

The input of an algorithm is what gets passed into the function when it is invoked. Typically, this will be some sort of primitive value: string, number, or object. The exact size of each might differ based on language, but we can figure in a general sense how much space is needed.

Example with Simple Inputs and Output

public int subtract(int a, int b) {
   return a - b;

( Note : We are using Java here so you can easily discern the data types, but this can pretty much go for any language.)

Take the above function. The purpose of this function is to take an input – in this case two ints (short for integers) and return an output, also an int.

In our input, we have two variables – int a and int b. Our returned value – an int – also takes up space as well. Because our integers are only evaluated once, we consider the space complexity here to be O(1) – constant time.

Example with More Complex Input

public int sumArray(int[] array) {
   int size = 0;
   int sum = 0;
   for (int i = 0; i < size; i++) {
       sum += array[i];
   return sum;

This function has an array as its input. The array, not knowing the length, has n indices. The two variables in the first two lines of the function are O(1) since they are evaluated only once. The sum is an integer, is also O(1). The Big O for space complexity is O(n) to dictate the space for the array.


The most efficient algorithm is one that takes the least amount of time and memory. It will be near impossible, if not impossible, though, to write an algorithm that will be able to satisfy both conditions. You ultimately have to sacrifice one for the other. The question becomes, which do you sacrifice?

The answer is: it depends. Everything depends on the requirements for the project or algorithm you are working on. If you only have minimal memory, you need to sacrifice time complexity to use the least space and vice versa.

About us: Career Karma is a platform designed to help job seekers find, research, and connect with job training programs to advance their careers. Learn about the CK publication.

What's Next?

Christina Kopecky

About the author: Christina is an experienced technical writer, covering topics as diverse as Java, SQL, Python, and web development. She earned her Master of Music in flute performance from the University of Kansas and a bachelor's degree in music with minors in French and mass communication from Southeast Missouri State. Prior to joining the Career Karma team in June 2020, Christina was a teaching assistant, team lead, and section lead at Lambda School, where she led student groups, performed code and project reviews, and debugged problems for students. Christina's technical content is featured frequently in publications like Codecademy,, and Educative.

Skip to main content