Reputation: 1493
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?
Upvotes: 5
Views: 10890
Reputation: 372754
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 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!
Upvotes: 7