I was doing a hackerrank question that requires me to find out the number of shifts that need to occur to sort an array using Insertion Sort without actually sorting the array with insertion sort because otherwise that would be O(n^2) time-complexity! Here is my code that gets timed out. From what I know, calling the headSet method n times should come to around O(n logn).
static class MyComp implements Comparator<Integer>{
@Override
public int compare(Integer o1, Integer o2) {
return o1 <= o2 ? -1: 1;
}
}
// Complete the insertionSort function below.
static int insertionSort(int[] arr) {
SortedSet<Integer> set = new TreeSet<>(new MyComp());
int count=0;
for(int i=arr.length-1; i>=0;i--){
set.add(arr[i]);
int pos = set.headSet(arr[i]).size();
// System.out.println(pos);
if(pos>0){
count=count+pos;
}
}
return count;
}
The complexity of creating a headset is O(1)
Why?
Because a headset is not a new set. It is actually a view of an existing set. Creating one doesn't involve copying the original set, and doesn't even involve finding the "bound" element in the set.
Thus, doing it N times is O(N).
However, the reason that your code is not O(N) is that
set.headSet(someElement).size();
is NOT O(1). The reason is that the size() method on a subset view of a TreeSet is computed by counting the elements in the view.
(AFAIK, this is not stated in the javadocs, but you can deduce it from looking at the source code for TreeSet and TreeMap.)