CODEWITHSUNDEEP
javaarraystime-complexitybig-ocontiguous
danielpeterson
danielpeterson

Reputation: 1

Determining the time complexity of Java code

I am working on a Java practice interview problem for finding the number of Contiguous Subarrays. I have a working solution, and just want to make sure I understand the time complexity of my answer:

  //solution is called with array of n length like this:
    countSubarrays([3,4,1,6,2])

  int[] countSubarrays(int[] arr) {
    System.out.println(Arrays.toString(arr));
    
    int[] ret = new int[arr.length];
    //for each index:
    for(int x = 0; x < arr.length; x++){
      int max = arr[x];
      System.out.println("arr["+x+"]="+max);
      
      //try going forward
      List<Integer> forwardList = new ArrayList<Integer>();
      for(int y = x; y < arr.length; y++){
        if(arr[y] <= max){
          forwardList.add(arr[y]);
        }else{
          break;
        }
      }
      System.out.println("forwardList="+forwardList);
      
      //try going backwards
      List<Integer> backwardList = new ArrayList<Integer>();
      for(int y = x; y >= 0; y--){
        if(arr[y] <= max){
          //add to start of list
          backwardList.add(0, arr[y]);
        }else{
          break;
        }
      }
      System.out.println("backwardList="+backwardList);
      
      //count number of contiguous subarrays
      int count = (forwardList.size() + backwardList.size()) -1;
      ret[x]=count;
      System.out.println("count: "+count+"\n");
    }

      return ret;
  }

If the input array is of n length, and my code solution features a for loop counting from 0 to n ( int x ), as well as two nested for loops counting forward and backwards until a larger int is found, would this mean my functions time complexity is O(n^2)?

I came to this solution when thinking that in the worst case scenario, my function would be going backwards and forwards the entire length of the array, but this would only happen once inside my int x for loop, so I wasn't sure if the time complexity was O(n) linear time or O(n^2) n squared.

Thanks

Upvotes: 0

Views: 242

Answers (1)

Joseph Balnt
Joseph Balnt

Reputation: 140

The simplified time complexity of this code would be O(n^2), where n is the size of the array. This is because you are iterating through 2 * (1 + 2 + ... + n) times. (There is a 2 because you have 2 for loops inside the first one). This would be O(2n(n-1)/2) = O(n*(n-1)), which simplifies to O(n^2).

Upvotes: 2

Related Questions