# Isn't allocating a same size array for result considered to be space complexity O(n)?

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)?

• 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.)? Jul 6, 2023 at 1:06
• 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? Jul 6, 2023 at 1:21
• 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. Jul 6, 2023 at 1:55
• 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. Jul 6, 2023 at 2:06
• @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 Jul 6, 2023 at 2:25

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.