Home > Software design >  What is the Big O notation for the following snippet of code?
What is the Big O notation for the following snippet of code?

Time:09-13

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;
}

CodePudding user response:

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.

CodePudding user response:

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)

  • Related