1. Input Storage:

   • The input array arr has n elements, where n is the length of the list. However, input space is not counted in auxiliary space complexity, so we focus on the additional memory used by the algorithm.

2. Auxiliary Space:

   • Variable max_val: We use this variable to store the current maximum value. No matter how large n is, this variable only takes up one unit of memory.
   • Loop Variable num: This variable stores each element in arr as we iterate through it. Again, this requires only one unit of memory, as num is overwritten in each iteration.

3. Total Space Complexity:

   • Since we’re only storing a fixed number of variables (max_val and num), the memory required does not increase with n. Therefore, the space complexity is O(1).

Example 2: Matrix Multiplication (Quadratic Space – O(n^2))

Now, let’s look at an algorithm for multiplying two matrices. Here, we’ll require memory that grows with the size of the input, leading to a quadratic space complexity.

Algorithm Code

1. Input Storage:

   • The matrices A and B are both n \times n matrices, so each one requires n^2 memory units. But as with the first example, we focus on auxiliary space and ignore the memory used to store inputs.

2. Auxiliary Space:

   • Output Matrix result: The result of multiplying two n \times n matrices is another n \times n matrix. We need to create this matrix to store the final product. Since result has n \times n elements, it takes up O(n^2) memory.
   • Loop Variables i, j, and k: These variables are used for iteration and only occupy a fixed amount of memory, which is O(1).

3. Total Space Complexity:

   • The dominant space usage here is the result matrix, which requires n^2 memory units. Therefore, the space complexity is O(n^2).