The space complexity of this algorithm that loops over an array

Question

I am asked to provide the asymptotic space and time complexity of the below algorithm in appropriate terms for an initial input number of arbitrary length (as distinct from a constant 12 digits).

1 for i = 2 to 12
2     if d[i] == d[i-1]
3        d[i] = (d[i] + 3) mod 10

This algorithm is apply for a number that has 12 digits, each digit is stored in the array d[] (so we have d[1], d[2],... d[12])

I figured out the time complexity is O(n) but how do I determine the space complexity?

Answer 1

Typically, to measure space complexity, you want to look at how much extra space is required to hold all the information necessary to execute the code. The challenge is that you can often reuse space across the lifetime of the code execution.

In this case, the code needs extra space to store

• The values of temporary calculations in the loop,
• The value of i, and
• Miscellaneous data like the program counter, etc.

The last two of these take up O(1) space, since there's only one i and constant space for auxiliary data like the stack pointer, etc. So what about the first? Well, each iteration of the loop will need O(1) space for temporary variables, but notice that this space can get reused because after each loop iteration finishes, the space for those temporaries isn't needed anymore and can be reused in the next iteration. Therefore, the total space needed is just O(1).

(A note... are you sure the time complexity is O(n)? Notice that the number of iterations is a constant regardless of how large the array is.)

Hope this helps!