-2

The code below is of a java method that iterates through a for loop, also creating a new array every time. I believe the code without the new array instantiation is O(N) but with the new array declaration, I am not sure.

int[] reverseArray(int[] a) {
  int[] result = new int[a.length];
  for (int i = 0; i < a.length; i++) {
    result[a.length - 1 - i] = a[i];
  }
  int[][] 2DArray = new int[a.length][a.length/2];
  // do something with 2DArray
  return result;
}
smac89
  • 39,374
  • 15
  • 132
  • 179
ksuk333
  • 9
  • 5

2 Answers2

0

Your reverseArray() method, ignoring the "do something with 2DArray" portion, which is not shown, is O(N) both in space complexity and time complexity. It walks down the input array once, and copies it backwards into an output array.

Tim Biegeleisen
  • 502,043
  • 27
  • 286
  • 360
  • The question is asking for space complexity* sorry I forgot to mention. – ksuk333 Sep 12 '22 at 16:07
  • Then you need to reveal the "do something" code as well. Besides this, you only have `O(N)` space complexity, which is the space needed for allocating the new reversed array. – Tim Biegeleisen Sep 12 '22 at 16:08
  • The do something code is not specified, as it is all the question gives me. – ksuk333 Sep 12 '22 at 16:30
  • The declaration of the 2D array is, as you have already pointed out, `O(N^2)` in storage. The unshown code is not relevant from a storage point of view if it does not further allocate anything. – Tim Biegeleisen Sep 12 '22 at 16:31
0

Instantiating the result array is O(n), the loop is O(n), but instantiating the 2D array would be O(n^2) since it will take up a.length * a.length / 2 ints in memory, so the overall runtime would be O(n^2)

Rubydesic
  • 3,386
  • 12
  • 27
  • Creating the 2D array as shown is not `O(n^2)`. We are not shown how the elements of the 2D array are initialized, if at all. – h0r53 Sep 12 '22 at 16:03
  • space complexity and runtime complexity are completely separate – smac89 Sep 12 '22 at 16:03
  • The question is asking for space complexity* sorry I forgot to mention. – – ksuk333 Sep 12 '22 at 16:07
  • 1
    @h0r53 The memory for the 2d array is zeroed, which requires O(n^2). This is not C where you can have uninitialized memory. – Rubydesic Sep 12 '22 at 16:12
  • @h0r53 You're not correct. The moment you've initialized it memory has already been allocated. So the answer in the context of the question is correct. – Abhishek Tyagi Sep 13 '22 at 04:18
  • @AbhishekTyagi that was already discussed in comments when this answer was provided. However, the relevant comments have been deleted by someone, likely because it was becoming off topic. Either way, The overall runtime is not `O(n^2)` based on the code that has been provided. Since, as you've noted, the 2D array is by default 0-initialized, the implicit initialization is not `O(n^2)` because there are ways to 0-initialize a block of contiguous memory more efficiently. The code *as shown at the time the OP made the question* has `O(n)` runtime and `O(n^2)` space complexity. – h0r53 Sep 13 '22 at 15:02
  • @h0r53 What are these ways to zero-initialize a block of memory more efficiently than O(n) where n is the size of the memory being initialized? – Rubydesic Sep 13 '22 at 18:40
  • @Rubydesic Would you consider `calloc(n, sizeof(int))`, `mmap`, or `VirtualAlloc` to be `O(n)` operations? Yes, we are talking about Java here, but under the hood allocating an array with `new int[n]` likely calls a lower level routine such as `calloc`. If you can show that Java's `new int[n]` truly takes `O(n)` then I'm with you. Otherwise, I wouldn't assume the underlying implementation. Part of the reason why `calloc` isn't O(n) is because it uses known-zeroed pages from the OS. – h0r53 Sep 13 '22 at 19:57
  • @Rubydesic "What is the time complexity of Java's array initialization" is an interesting conversation. [Here](https://stackoverflow.com/questions/5640850/java-whats-the-big-o-time-of-declaring-an-array-of-size-n) is a S.O. question that discusses it. If you review the answers in full you'll see *it depends* and the JVM doesn't seem well defined for that specific operation; In some cases it is O(n), in others it isn't. It doesn't have to be O(n) if some lower level methods that I mentioned before are used, but for the sake of OP's question I wouldn't say it's definitively `O(n^2)`. – h0r53 Sep 13 '22 at 20:05
  • In fact, if the array is not actually used, then the JVM likely doesn't zero-initialize the allocated memory as part of an optimization. The OP didn't provide any code suggesting how the array was used, so again it's impossible to say for certain based on what was given. I'm not trying to debate you, I do think this is an interesting conversation, I'm just pointing out that we can't assume the code provided is `O(n^2)`. – h0r53 Sep 13 '22 at 20:09