What is the space complexity of the following Java code?

public int[] foo(int[] x) {
   x = new int[x.length];
   // Do stuff with x that does not require additional memory
   return x
}

Is it O(1) or O(N)? I've seen both answers. But I can't understand how it could be O(1). I would guess that it's O(N). We create a new array of the same size while the original array might still exist. Thus the original array is not replaced, i.e. we allocated additional storage space that increases linear with the length N of the input array. Am I correct?

CodePudding user response：

The semantic of this piece of code is unsure, as the language is not specified. In any case, O(1) isn't possible because one allocates a new array at the same time that the original exists. (In a garbage collected language, one could imagine, with a lot of bad faith, that x is deallocated then immediately reallocated at the same place.)

CodePudding user response：

O(N) with details that are highly dependent on various external factors such as your operating system.

A naive implementation requires actually zeroing out memory and assigning it. If the space requested is small, and particularly if you've already freed a good place to put it, this is probably what is going to happen. That operation is O(N).

If the space requested is large, you're probably just going to set up page table entries and NOT allocate any space. This is again O(N), but with extremely good constants. As you use the memory it actually has to get assigned, which is no faster than doing it up front. (It is actually slower.) But, in the meantime, being slow to use up memory is good for reducing contention on RAM.