CODEWITHSUNDEEP
java
Austin Yan
Austin Yan

Reputation: 21

The running time of the algorithm

I did not figure out why the running time the Algorithm below is O(nlogn). Could anyone help me out?

public static boolean unique2(int[] data) {
  int n= data.length;
  int[] temp= Arrays.copyOf(data,n);
  Arrays.sort(temp);
  for (int j=0; j<n-1;j++)
    if (temp[j]==temp[j+1])
      return false;
  return true;
}

Upvotes: 2

Views: 57

Answers (2)

Nowhere Man
Nowhere Man

Reputation: 19545

This algorithm includes two main parts:

  1. Sorting the array using standard Arrays.sort for int[] array.

Under the hood, it uses a Dual-Pivot Quicksort algorithm with average O(n log n) time complexity.

  1. for loop to find any duplicate value in the sorted array with O(n) complexity which is "absorbed" by the greater complexity of sorting.

Thus, the resulting complexity is O(n log n).

Upvotes: 2

Eran
Eran

Reputation: 393781

Arrays.sort(temp) takes O(nlogn), since that's the running time of the most efficient sorting algorithms, and the JDK implementation uses an O(nlogn) algorithm.

The other parts of that method - Arrays.copyOf(data,n) and the loop, take O(n) time, since they iterate over the array one time.

Hence the overall running time is O(nlogn).

Upvotes: 3

Related Questions