Space Complexity

In the previous section, we learned about Time Complexity. Now, we will learn about Space Complexity.

💾 What is Space Complexity?

Space Complexity is used to measure the amount of memory an algorithm uses during its execution based on the size of the input data.

so what does this mean? For smaller input dataset, the algorithm may need less memory to execute, but as the input dataset becomes larger, the algorithm may require more memory to execute.

🔁 How Space Complexity is different from Time Complexity?

Time complexity represents how the execution time of an algorithm changes with the size of the input data, while space complexity represents how the memory usage of an algorithm changes with the size of the input data.

🧠 Which memory is considered in Space Complexity?

When we talk about space complexity, we consider Main memory (RAM) used by the algorithm during its execution. Because the algorithm use RAM to store variables, data structures, and other information needed for its execution.

Lets see some common space complexities in detail!

⚙️ O(1) space complexity

O(1) space complexity:

• known as constant space complexity
• means that the algorithm uses a fixed amount of memory regardless of the size of the input data

🧪 Example of O(1) space complexity:

Calculate the sum of all elements in an array.

public void sumOfArray(int[] arr) {
    int sum = 0; // This variable takes O(1) space
    for (int i = 0; i < arr.length; i++) {
        sum += arr[i];
    }
    System.out.println("Sum: " + sum);
}

In this example:

• The variable sum always takes same space in memory, regardless of the size of the input array arr.
• Then we just loop through the array to calculate the sum.
• We do not store any other things in memory that depend on the size of the input array.

So, the space complexity of this algorithm is O(1).

⚙️ O(n) space complexity

O(n) space complexity:

• known as linear space complexity
• means that the algorithm uses an amount of memory that grows linearly with the size of the input data

🧪 Example of O(n) space complexity:

Copy all elements from one array to another array.

public int[] copyArray(int[] arr) {
    int n = arr.length;
    int[] newArr = new int[n]; // This array takes O(n) space
    for (int i = 0; i < n; i++) {
        newArr[i] = arr[i];
    }
    return newArr;
}

In this example:

• The new array newArr variable will always take space in memory based on the size of the input array arr.
• So, if the input array has n elements, the new array will also have n elements.
• then we have taken n variable to store the length of the array, which takes always same space in memory, regardless of the size of the input array.
• then we just loop through the array to copy the elements.
• We do not store any other things in memory that depend on the size of the input array.

So, the space complexity of this algorithm is O(n) + O(1) and we can ignore O(1) so the final space complexity is O(n).

⚙️ O(n^2) space complexity

O(n^2) space complexity:

• known as quadratic space complexity
• means that the algorithm uses an amount of memory that grows quadratically with the size of the input data

🧪 Example of O(n^2) space complexity:

Create a 2D array (matrix) of size n x n.

public int[][] createMatrix(int n) {
    int[][] matrix = new int[n][n];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            matrix[i][j] = i + j;
        }
    }
    return matrix;
}

In this example:

• The 2D array matrix variable will always take space in memory based on the size of the input n.
• So, if n is the size of one dimension, the total number of elements in the 2D array will be n * n, which is n^2.
• then we just loop through the array to fill the elements.
• We do not store any other things in memory that depend on the size of the input n.

So, the space complexity of this algorithm is O(n^2).

⚙️ O(log n) space complexity

O(log n) space complexity:

• known as logarithmic space complexity
• means that the algorithm uses an amount of memory half or reduces with the size of the input data

🧪 Example of O(log n) space complexity:

Recursive function to calculate the power of a number.

function power(x, n) {
  if (n === 0) return 1;
  const half = power(x, Math.floor(n / 2));
  if (n % 2 === 0) return half * half;
  return half * half * x;
}

In this example:

• The function power uses recursion to calculate the power of a number.
• Each recursive call reduces the size of the input n by half.
• The space used by the call stack is proportional to the logarithm of the input size.

So, the space complexity of this algorithm is O(log n).

📊 Space complexity in increasing order

Here are some common space complexities we may see. These are increasing in order means the first one is the best and the last one is the worst.

✅ Conclusion

In this section, we learned about Space Complexity in detail. We learned what is space complexity, how it is different from time complexity, which memory is considered in space complexity and how to calculate space complexity with examples of O(1), O(n), O(log n), O(n^2) and more.