0
$\begingroup$

It is related to this question: https://leetcode.com/problems/product-of-array-except-self/

And assuming we cannot alter the original array, but have to allocate a same size array to store the results, that is, if the input array is 200GB, we need to allocate a 200GB array. Input 800GB, allocate extra 800GB. Input 16TB, allocate 16TB. (suppose now or one day the RAM or virtual memory has that much capacity).

However, according to the problem description:

Follow up: Can you solve the problem in O(1) extra space complexity? (The output array does not count as extra space for space complexity analysis.)

And some people putting down a solution also agree, essentially, allocating that extra array for the result doesn't count and it is space complexity O(1).

However, we do in practice have to allocate the 16GB, 800GB, 16TB, or whatever the input size is.

The question is, when doing this, is the space complexity O(1) or O(n)?

$\endgroup$
7
  • $\begingroup$ I'm sorry if I do not seem to get the main point of your question. Are you asking why the size of the output array is not considered? If so, isn't it already an assumption in your problem that (The output array does not count as extra space for space complexity analysis.)? $\endgroup$
    – Russel
    Jul 6, 2023 at 1:06
  • $\begingroup$ yes, why the size of the output array is not considered? You need 16GB or 800GB like I said. We cannot just "dream" of it. So when we need it, why is it not part of the cost? $\endgroup$ Jul 6, 2023 at 1:21
  • 2
    $\begingroup$ The space complexity is $O(1)$ according to their definition. The statement "The output array does not count as extra space for space complexity analysis" is a part of their definition of space complexity. It might or might not match your expected definition of space complexity, which is irrelevant: their definition overrides yours. If your question is "In other settings, do we count the output towards space complexity ?", then the answer varies depending on the settings, e.g. some models assume unbounded write-only output tape, which doesn't count towards space complexity. $\endgroup$
    – Dmitry
    Jul 6, 2023 at 1:55
  • 1
    $\begingroup$ The way I understand it, the problem is asking you to ignore the cost of the output array in your algorithm since any algorithm for the problem will need the output array based on the problem specification. What matters then is the additional size the algorithm for the problem will add on top of the size of the input and output. $\endgroup$
    – Russel
    Jul 6, 2023 at 2:06
  • $\begingroup$ @Dmitry how can you redefine something like this. And the statement "The output array does not count as extra space for space complexity analysis" sound like it is universal, not for this problem only. And for this problem, you cannot spit out the numbers sequentially. You have to move to the front and then to the back of the array. So if you use tape, you have to rewind all the way, and then fast forward all the way, yes, possibly for 200,000 feet of tape, and then repeat $\endgroup$ Jul 6, 2023 at 2:25

1 Answer 1

2
$\begingroup$

It is normally assumed that the space for input and output is already allocated and neither do count in the estimation of the complexity. So you won't allocate an extra array.

This is logical, as you need the input and output storage anyway. What matters is additional resources that an algorithm would require.


A special case is given by MergeSort. Indeed, sorting algorithms are meant to be in-place, i.e. input and output coincide. This is why MergeSort is said to require $O(n)$ space.

$\endgroup$
2
  • $\begingroup$ the question can say, "let's not count the space needed for the result array", and give an algorithm which requires O(1) space. That's fine. However, it is not saying that. It is saying, ok, we need to allocate n spaces for the results and let's call it O(1) $\endgroup$ Jul 7, 2023 at 23:24
  • $\begingroup$ @StefanieGauss: where is this said ?? $\endgroup$
    – user16034
    Jul 8, 2023 at 10:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.