The reader is advised to read all the lessons (tutorials) in this full course, in the order presented.

The estimate of space complexity is the same, as with time complexity, using big-O notation. However, n in space complexity refers to number of memory locations. An input of one variable, is O(1) space complexity. An array input of n locations is O(n) space complexity. A two-dimentional array of size n² is O(n²) space complexity. A three-dimentional array of size n³ is O(n³) space complexity; and so on. However space complexity is not limited to only the input. It also involves auxiliary space.

Auxiliary Space is space needed by the algorithm beyond the input space, in other to function. Temporary space is also auxiliary space.

Space Complexity of an algorithm is defined as the total space taken up by the algorithm with respect to the input size. The big-O notation gives the estimate.

Space complexity consists of both auxiliary space and space used by input.

Unfortunately many documents give just the auxiliary space for space complexity without the input space. That is not strictly correct.

The rest of the sections in this tutorial, will be similar to their counterparts in the previous time-complexity tutorial.

Constant Space - O(1)

Consider the following program:

    #include <stdio.h>
    
    void solution () {
        int result = 6;
        printf("%i\n",result);
    }

    int main(int argc, char **argv)
    {
        solution();

        return 0;
    }

The output is 6. The space complexity is O(1) for the single variable, result. This involves only the auxiliary space. There is no input space: the calling function sends no argument.

Linear Space - O(n)

Consider the following program:

    #include <stdio.h>
    
    void solution(int arr[]) {
        int arrA[] = {arr[0], arr[1], arr[2], arr[3], arr[4]};
        printf("%i %i %i %i %i", arrA[0], arrA[1], arrA[2], arrA[3], arrA[4]);
        printf("\n");
    }

    int main(int argc, char **argv)
    {
        int arry[] = {1, 2, 3, 4, 5};
        solution(arry);

        return 0;
    }

The output is:

    1 2 3 4 5

Strictly speaking, the space complexity in this program is O(2n); that is, O(n) for the input array, arry and O(n) for the array, arrA in the algorithm (function). However, the coefficient which is the multiple of the space complexity expression, is usually omitted when quoting the space complexity. So, the space complexity for the above problem is:

    O(n)

which ends up just referring to the auxiliary space. Do not forget that the array, arry is different from the array, arrA, while the array, arry is the same as the array arr (in the parameter parentheses – they have the same start reference variables).

Logarithmic Space – O(log n)

The mathematical symbol, =>, means "this implies that".

Now,

      8 = 2 x 2 x 2
=>    8 = 23

In this second math statement, 2 is called the base, 3 is called the index and 8 is just called the number (number of interest). So 8 equals 2 raised to the power (index) 3, because 2 is multiplied by itself 3 times to give 8.

The second mathematical statement above, can be rewritten as:

        log2 8 = 3

read as, log to the base 2 of 8 equals 3. The word, log, is of the math topic, logarithm. There are three mathematical statements above (in this section). The second and third are two different ways of writing the same thing. The two different ways, each has its pros and cons.

From out of 8 possible repetitions of the main operation in a function, if the main operation repeats 3 times, then the time or space complexity is written as:

   O(log2 n)

using the Big-O notation, where n in this case is 8. The subscript 2 is optional to write. The logarithmic space, O(log n) is usually less than half the linear space, O(n), e.g 3 is less than half of 8, which is 4.

For code example of logarithmic space, with the number 8 as the upper limit, consider the following program:

    #include <stdio.h>
    
    void solution(int z) {
        int b = z;
        int c = 2;
        int d = 3;
        
        printf("%i %i %i", b, c, d);
        printf("\n");
    }

    int main(int argc, char **argv)
    {
        int a = 1;
        solution(a);

        return 0;
    }

The output is:

    1 2 3

The space complexity is actually,

    O(4) = O(log2n)

out of an assumed 8 expected locations, by the user. Many documents will give the space complexity here as,

    O(3) = O(log2n)

referring to the auxiliary space only, without the input space. The input space complexity is O(1), for the single variable, "int a = 1;".

Quadratic Space - O(n²)

In the alphabet, A, B, C, D, E, F, G, H are characters, and each is less than (comes before) 'I'. Consider the following program:

    #include <stdio.h>
    
    void solution() {
        char twoDArray[8][8];
        for (char i='A'; i<'I'; i++) {
            for (char j='A'; j<'I'; j++) {
                twoDArray[i][j] = j;
                printf("%c ", j);
            }
            printf("\n");
        }
    }

    int main(int argc, char **argv)
    {
        solution();

        return 0;
    }

The output is:

    A B C D E F G H 
    A B C D E F G H 
    A B C D E F G H 
    A B C D E F G H 
    A B C D E F G H 
    A B C D E F G H 
    A B C D E F G H 
    A B C D E F G H 

There is no input and so no input space. The auxiliary space and the total space complexity is:

    O(64) =  O(82) = O(n2)

which comes from the 2D array and not from the printf statement.

n.log₂n Space

n.log₂n means, n x log₂n . The mathematical symbol, ∴ means, therefore.

From above,

     8 = 2 x 2 x 2
=>   8 = 23
=>   log2 8 = 3

Now,

    if n = 8, then O(n2) = 64 operations = O(82).

    if n = 8, it means log2 8 = 3;
    ∴ n x log2n = 8 x 3 = 24

64 = 8²

There are 24 main operations for (8xlog₂ 8) time. 24 is less than half of 64, which is 32. 24 is greater than 3, which equals log₂8 .

So, O(n.log₂n) space complexity lies between O(log₂n) and half of O(n²) , generally.

For code example of O(n.log₂n) time, with the number 8, consider the following program:

    #include <stdio.h>

    void solution() {
        int N = 8, Q = 8;
        int twoDArray[Q][N];
        for (int i=0; i<Q; i++) {
            while (N > 1) {
                N = N / 2;  //integer division
                twoDArray[i][N] = N;
                printf("%i, ", N);
            }
            printf("\n");
            N = 8;
        }
    }

    int main(int argc, char **argv)
    {
        solution();

        return 0;
    }

The output is:

4, 2, 1, 
4, 2, 1, 
4, 2, 1, 
4, 2, 1, 
4, 2, 1, 
4, 2, 1, 
4, 2, 1, 
4, 2, 1, 

There is no input and so no input space. The auxiliary space and total space complexity is:

    O(3 x 8) = O(24) = O(3 x 23) = O(n.log2n)

which comes from the 2D array and not from the printf statement.

n + m Linear Space : O(n + m)

For code example of n + m linear time, with the number n = 8, consider the following function:

    #include <stdio.h>

    void solution() {
        int start = 1;
        int oneDArryA[7];
        for (int i=start; i<8; i++) { 
            oneDArryA[7] = i;
            printf("%i ", i);
        }
        
        printf("\n");

        int oneDArryB[9];
        for (char i='A'; i<'J'; i++) {  //'I' is 9th letter in alphabet
            oneDArryB[i] = i;
            printf("%c ", i);
        }
        printf("\n");
    }

    int main(int argc, char **argv)
    {
        solution();

        return 0;
    }

The output is:

    1 2 3 4 5 6 7
    A B C D E F G H I

There is no input and so no input space. The auxiliary space and total space complexity is:

    O(7+9) = O(n+m)

which comes from the 2D array and not from the printf statement. The contribution of the memory location of the start variable, in the solution function, is ignored.

Even if there were three non nested for-loops, as in the following program, the space complexity would still be given as O(n + m) :

    #include <stdio.h>

    void solution() {
        int start = 1;
        int oneDArryA[7];
        for (int i=start; i<8; i++) { 
            oneDArryA[7] = i;
            printf("%i ", i);
        }
        printf("\n");
        int oneDArryB[8];
        for (char i='A'; i<'I'; i++) {  //'I' is 9th capital letter in alphabet
            oneDArryB[i] = i;
            printf("%c ", i);
        }
        printf("\n");
        char oneDArryC[9];
        for (char i='a'; i<'j'; i++) {  //'j' is 10th small letter in alphabet
            oneDArryC[i] = i;
            printf("%c ", i);
        }
        printf("\n");
    }

    int main(int argc, char **argv)
    {
        solution();

        return 0;
    }

The output is:

    1 2 3 4 5 6 7 
    A B C D E F G H 
    a b c d e f g h i 

Nuance to do with ½n, 2n, etc.

In an algorithm where the upper limit is 8 = n (linear space), 4 main operations = ½n or 16 main operations = 2n, is given simply as O(n). In other-words, fractions and multiples (coefficients) in front of space complexity expressions are avoided.

Approximation of Space Complexity

Space complexity, of O(10) may actually have 8 or 9 memory locations, or even 11 or 12 locations, or the 10 itself, though the maximum limit of 8 is aimed at. In many cases it would have 8 locations or less.

Exercise

Problem 1: You are given an integer n. Count the total of 1 + 2 + . . . + n, in O(n²) time. Also give the space complexity in big-O notation.

Solution

The following program has one test case in the main() function (read the code and comments in the whole program). In the function, 1 is 1; 2 is 1 + 1; 3 is 1 + 1 + 1; 4 is 1+1+1+1; etc.

    #include <stdio.h>

    int slow_solution (int N) {  //using zero based indexing 
        int result = 0;
        for (int i=0; i<N; i++) {
            for (int j=0; j < i+1; j++) {  //i=0 or j=0 refers to the first element, 1
                result += 1;               //i=1 or j=1 refers to the second element, 2, etc.
            }
        }

        return result;
    }

    int main(int argc, char **argv)
    {
        int n = 4;
        int res = slow_solution(n);
        printf("%i\n",res);
        
        return 0;
    }

The output is 10, for input of N = 4.

The input space complexity is O(1) for the variable, "int n = 4;" . The auxiliary space complexity is also just O(1), for the variable, "int result = 0;" . The nested for-loop uses only this variable. Any extra temporary variable needed by the algorithm function, is ignored in this case. Strictly speaking, the space complexity should be given as:

    O(2 x 1)

for both the input space and auxiliary space. However, conventionally, it is given as:

    O(1)

Problem 2: Repeat the above problem for the time complexity of O(n).

Solution

The following program has one test case in the main() function (read the comments in the whole program). The function does 1 + 2 + 3 + 4 = 10.

    #include <stdio.h>

    int fast_solution (int N) {  //using zero based indexing 
        int result = 0;
        for (int i=0; i<N; i++) {
            result = result + (i + 1);  //1=0+1; 2=1+1; 3=2+1; etc.
        }

        return result;
    }

    int main(int argc, char **argv)
    {
        int n = 4;    //1 + 2 + 3 + 4 = 10
        int res = fast_solution(n);
        printf("%i\n",res);

        return 0;
    }

The output is 10; same as above, for input of N = 4.

The space complexity for this program is still given as:

    O(1)

which is not strictly correct.

Problem 3: Repeat the above problem for the constant time complexity, O(1).

Solution

This is a mathematical Arithmetic Progression, with the first term, a = 1, and common difference, d = 1. The sum, S_n of the first n terms, of an arithmetic progression, is given by,

    Sn = n/2[2a + (n-1)d]

This formula is one main operation and should be coded as such. The following program has one test case in the main() function (read the comments for the whole program):

    #include <stdio.h>
    
    int model_solution (int n) {  //formula: sum of arithmetic progression, with first element, 1 and difference, 1

        int result = n/2*(2*1 + (n-1)*1);  //one operation, without repetition in any loop

        return result;
    }

    int main(int argc, char **argv)
    {
        int n = 4;  //sum = n/2*(2*1 + (n-1)*1)
        int res = model_solution(n);
        printf("%i\n",res);

        return 0;
    }

The output is 10; same as above, for input of N = 4. There is only one main operation here.

The space complexity for this program is still given as:

    O(1)

which is not strictly correct. It cannot be given as O(10) = O(n), because the number of obvious identifiable memory locations, is not up to 10.

Space Complexity in General

Memory limits provide information about the expected space complexity. The programmer can estimate the number of variables that he can declare in his programs. In short, if he has constant numbers of variables, he also has constant space complexity: in Big-O notation this is O(1). If he needs to declare an array with n elements, he has linear space complexity - O(n).

More specifically, space complexity is the amount of memory needed to perform the computation. It includes all the variables, both global and local, dynamic pointer data-structures, and in the case of recursion, the contents (space) of the stack. Depending on the convention, input data may also be included. Space complexity is more tricky to calculate than time complexity, because not all of these variables and data-structures may be needed at the same time. Global variables exist and occupy memory all the time; local variables (and additional information kept on the stack) will exist only during invocation of the function. There are also temporary variables needed by the algorithm.

Conclusion

Space Complexity of an algorithm is defined as the total space taken up by the algorithm with respect to the input size. The big-O notation gives the estimate.