18.4. Space Complexity Analysis

Now, let’s briefly focus on space complexity analysis. Suppose you have a set of algorithms that all solve the same problem. In order to analyze each of them, we first need to do the following:

1. Define the problem size = n; then

2. Define the unit of measurement.

We need to define the problem size and the unit the same way for all of the algorithms we wish to compare based on their space complexities so that it’s a fair comparison.

To determine these space complexities, we need to do the following:

3. Derive a spacing function, S(n), that reflects the number of units required to solve the problem in terms of the problem size.

4. Classify S(n) into a complexity class based on the formula for the function.

That’s it! Those four steps are what you need to do in order to perform a space complexity analysis for an algorithm. The trickiest part is usually the third step, which is what most of this tutorial will focus on. We will have a separate tutorial that focuses exclusively on the fourth step.

18.4.1. Example Problems

1. Iterative Example

   Here is an algorithm that solves the problem of iteratively printing all characters of a string:

   void printS(String s) {
       for(int i = init; i < s.length(); i++) {
           System.out.println(s.charAt(i));
       } // for
   } // printS
   

   Considerations:

   • As usual, let’s define the problem size as the input length. Therefore, let n = s.length().

   • Let’s also define the unit of measurement as bytes.

   Towards a Sample Solution:

   • What is S(n) if the units are bytes? Without loss of generality, we’ll assume that init is initially supplied a value of 0. To answer this question, let’s first consider how much memory the string itself takes and use that as a starting amount for S(n):

     S(n) = (2 * n) + ?
     

     This starting value is derived from the fact that a char in Java is two bytes. Additionally, each of the local variables for the method take up a spot in the method’s call stack frame:

     Variable	Description
     s	8-byte local reference variable
     i	4-byte local int variable

     Therefore, we get the following spacing function:

     S(n) = 2 * n + 12
     

2. Recursive Example

   Here is an algorithm that solves the problem of recursively printing all characters of a string:

   void printS(String s) {
       if (!s.isEmpty()) {
           System.out.println(s.charAt(0));
           printS(s.substring(1));
       } // if
   } // printS
   

   Considerations:

   • As usual, let’s define the problem size as the array length. Therefore, let n = s.length().

   • Let’s also define the unit of measurement as bytes.

   Towards a Sample Solution:

   • What is S(n) if the units are bytes? Without loss of generality, we’ll assume that init is initially supplied a value of 0. To answer this question, let’s first consider how much memory the string itself takes and use that as a starting amount for S(n):

     S(n) = 2 * n + ?
     

     This starting value is derived from the fact that a char in Java is 2 bytes. Additionally, each of the local variables for the method takes up a spot in the method’s call stack frame:

     Variable	Description
     s	8-byte local reference variable

     This provides us with something like this:

     S(n) = 2 * n + 8 + ?
     

     However, we’re not done! In order to complete its work, the recursive printR method calls itself on a slightly smaller printS method:

     S(n) = 2 * n + 8 + S(n - 1)
     S(0) = 8
     

     This is known as a recurrence relation, and it does not have an obvious, intuitive solution. You should learn how to solve relations such as this in a Discrete Mathematics course. For now, we’ll provide you with the solution:

     S(n) = (n + 1)(n + 8)
     

     This can simplified to the following if we’re concerned with identifying an upper bound:

     S(n) ≤ n^2 + 9n + 8
     

Congratulations! You now have a basic understanding of the first three steps involved in an algorithm analysis! We will have a separate tutorial that focuses exclusively on the fourth step.