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?

@MitchWheat: what do you mean "extra space"? the question just says so... I think it is not supposed to use extra space — Hien Tran
– Hien Tran, Commented Sep 15, 2013 at 5:09
@MitchWheat probably means, does it allocate more storage than is provided by the input. I doubt that he's referring to the extra spaces between i and 1 in the second line of the program. — James Waldby - jwpat7
– James Waldby - jwpat7, Commented Sep 15, 2013 at 6:18
@HienTran if you read through this Q&A, stackoverflow.com/questions/18686121/…, you should get a better understanding of space and time complexity. — TooTone
– TooTone, Commented Sep 15, 2013 at 10:38

templatetypedef · Accepted Answer · 2013-09-15 22:57:26Z

7

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!

answered Sep 15, 2013 at 22:57

templatetypedef

376k112 gold badges954 silver badges1.1k bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Sysyphus Over a year ago

My reading of the question is that given an algorithm for 12 digits, what is the time complexity for the general case of n digits? Which is indeed O(n). Since asking for the time complexity of an algorithm given a specific constant input size tends to be rather pointless.

templatetypedef Over a year ago

@Sysyphus- It's hard to say from just what's given, but many instructors will give problems like this just to make sure students realize the answer is O(1) rather than O(n). If the algorithm was supposed to work in the general case, my guess is that it would probably be written so that the number of digits is variable.

Collectives™ on Stack Overflow

The space complexity of this algorithm that loops over an array

1 Answer 1

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related