Start learning free

LESSON 210 OF 409 · BIG O NOTATION

Space Complexity and Time Complexity in C++

Reading Read the full explanation

Space Complexity measures the total amount of memory that an algorithm or operation needs to run according to its input size.

Space Complexity is a parallel concept to Time Complexity. We express space complexity measurements using the Big-O notation, following the same guidelines like we do for time complexity.

Now let's learn how to compute space complexity by taking a few examples (written in pseudo-code, so they apply to any language):

Constant Space Complexity:

function add(a, b):
    sum = a + b
    return sum

In the example above, we use 3 number variables: a and b, which are input variables and sum, which is an auxiliary variable.

And because the space requirement is fixed (3 number variables), hence it is called Constant Space Complexity and is noted with O(1).

Linear Space Complexity:

function generate(n):
    numbers = empty list
    for i from 0 to n - 1:
        add i to the end of numbers
    return numbers

In the example above, we use an auxiliary vector numbers which is populated with n numbers.

Since the total space requirement is n numbers, the Space Complexity is increasing linearly with the increase in the input value n, hence it is called as Linear Space Complexity and is noted with O(n).

Quadratic Space Complexity:

function generate(n):
    numbers = empty list
    for i from 0 to n - 1:
        add an empty list to the end of numbers
        for j from 0 to n - 1:
            add j to the end of the row at index i
    return numbers

In the example above, we use an auxiliary 2D vector numbers of n rows and n columns.

Since the total space requirement is n^2 numbers, the Space Complexity is directly proportional to the squared of the input value n, hence it is called as Quadratic Space Complexity and is noted with O(n^2).

Extra/Auxiliary Space:

Sometimes Extra/Auxiliary Space is confused with Space Complexity. But Auxiliary Space is the extra space or the temporary space used by the algorithm during its execution (without taking the input values into account).

Space Complexity = Auxiliary Space + Input space

Let's see some examples:

function addAll(arr):
    sum = 0
    for each num in arr:
        sum += num
    return sum

In the example above, we have an input vector arr. If we denote its length by n, the Input Space is O(n).

However, we use only 2 auxiliary variables sum and num, so the Extra Space is O(1).

Next lesson

C++ · BIG O NOTATION

Space Complexity in C++, explained

Understanding the Problem

The core challenge of understanding space complexity lies in identifying how much additional memory an algorithm requires relative to its input size. This is significant in scenarios where memory resources are limited, such as embedded systems or large-scale data processing.

Common applications include optimizing algorithms for better performance and ensuring that programs run efficiently within the available memory constraints.

Potential pitfalls include confusing space complexity with time complexity and not accounting for all auxiliary space used by the algorithm.

Approach

To solve problems related to space complexity, follow these steps:

  1. Identify the input size and the variables used.
  2. Determine the auxiliary space required by the algorithm.
  3. Sum the input space and auxiliary space to get the total space complexity.

Let's discuss different approaches with examples:

Naive Solution

Consider a naive solution where we do not optimize for space. For example, creating multiple copies of data unnecessarily can lead to higher space complexity.

Optimized Solutions

Optimized solutions aim to reduce the auxiliary space used. For instance, using in-place algorithms where possible can significantly reduce space complexity.

Algorithm

Let's break down the algorithm for calculating the sum of an array with minimal space complexity:

#include <iostream>
#include <vector>

using namespace std;

// Function to calculate the sum of elements in an array
int sum(const vector<int>& arr) {
    int sum = 0; // Auxiliary variable
    for (int num : arr) {
        sum += num; // Accumulate the sum
    }
    return sum;
}

int main() {
    vector<int> arr = {1, 2, 3, 4, 5};
    cout << "Sum: " << sum(arr) << endl;
    return 0;
}

Code Implementation

Here is the C++ implementation of the sum function:

#include <iostream>
#include <vector>

using namespace std;

// Function to calculate the sum of elements in an array
int sum(const vector<int>& arr) {
    int sum = 0; // Auxiliary variable
    for (int num : arr) {
        sum += num; // Accumulate the sum
    }
    return sum;
}

int main() {
    vector<int> arr = {1, 2, 3, 4, 5};
    cout << "Sum: " << sum(arr) << endl;
    return 0;
}

Complexity Analysis

The time complexity of the sum function is O(n) because it iterates through the array once. The space complexity is O(1) for the auxiliary variable sum, plus O(n) for the input array, resulting in a total space complexity of O(n).

Edge Cases

Consider edge cases such as an empty array or an array with a single element. The algorithm should handle these gracefully:

#include <iostream>
#include <vector>

using namespace std;

// Function to calculate the sum of elements in an array
int sum(const vector<int>& arr) {
    int sum = 0; // Auxiliary variable
    for (int num : arr) {
        sum += num; // Accumulate the sum
    }
    return sum;
}

int main() {
    vector<int> arr1 = {};
    vector<int> arr2 = {10};
    cout << "Sum of empty array: " << sum(arr1) << endl;
    cout << "Sum of single element array: " << sum(arr2) << endl;
    return 0;
}

Testing

To test the solution comprehensively, include a variety of test cases:

  • Empty array
  • Array with one element
  • Array with multiple elements
  • Array with negative numbers

Using testing frameworks like Google Test can help automate and manage these tests effectively.

Thinking and Problem-Solving Tips

When approaching such problems, consider the following tips:

  • Break down the problem into smaller parts.
  • Identify the input size and auxiliary space used.
  • Optimize for space by using in-place algorithms where possible.
  • Practice solving similar problems to improve your skills.

Conclusion

Understanding space complexity is crucial for writing efficient algorithms, especially in memory-constrained environments. By analyzing and optimizing space complexity, you can ensure that your programs run efficiently and effectively.

Additional Resources

For further reading and practice problems, consider the following resources:

Keep going with C++About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
Start learning free