Space Complexity and Modifying the Data Set

Question

What is the space complexity of the following algorithm?

Given an array of n 32-bit signed integers, where each value is positive and less than two to the power of 30, negate all values in the array, then negate all values in the array a second time.

The question arose for me out of a discussion in the comment section here: Rearrange an array so that arr[i] becomes arr[arr[i]] with O(1) extra space

I am specifically interested in different opinions and definitions. I think subtle distinctions and definitions may be missing sometimes in some stackoverflow discussions on this subject.

Answer 1

You are confusing two different, though related, things: computer-theoretic space complexity of an algorithm, and practical memory requirements of a program.

Algorithms in computer science are normally not formulated in terms of integers of certain predefined size which is imposed by currently predominant computer architectures. If anything, they are parameterized by integer size. So "given an array of n 32-bit signed integers" should be replaced with "given an array of n k-bit signed integers".

Now if all integers of the input array are actually m<k bit wide, and all integers of the output array are also known to be m<k bit wide, and nothing else outside your algorithm imposes k bit wide integers, then sneaking k in the problem description is just cheating in order to make your complexity look better then it actually is. Likewise, saying "signed" if both input and output data is supposed to be positive is cheating.

Real-life programs don't have complexity, they have memory requirements. It is perfectly fine to say that your program does not use any extra memory if it only temporarily uses otherwise unused sign bits of your array elements. Just don't act surprised when one fine day you discover you have too large an array and you must pack it, so that it no longer has any unused bits. That is, you are reusing your algorithm in a different program with a different data representation, one that does not have any spare bits. Then you are forced to recall that the added space complexity of your algorithm is actually O(n).

Answer 2

Space complexity usually refers to the added space requirements for an algorithm, over and above the original data set itself. In this case, the original data set is the n 32-bit signed integers, so you're only concerned with extra storage above that.

In that case, that extra storage is is basically nothing, which translates to constant O(1) space complexity.

If you were required to create a separate array (negated, then negated again), it would be O(n) since the space required is in proportion to the original data set.

But, since you're doing the negations in-place, that's not the case.

Answer 3

Since you're interested in space complexity, the only relevant part of the question is:

"an array of n 32-bit signed integers"

From the above, the answer is pretty straightforward - O(n)

This whole blurb:

negate all values in the array, then negate all values in the array a second time

only affects the time complexity, which seems like a poorly crafted distraction in a homework assignment.