Search code examples
javaalgorithmcomplexity-theoryanalysis

How to analyze the growth of the following code?

I already know that the worst case complexity is N, and the best case is Mlog(M) but I just don't see how. Can anybody explain to me why this is the case and what different inputs would cause each case?

public static Iterable<Integer> topM(int[] a, int M){
int N = a.length;
MinPQ<Integer> pq = new MinPQ<Integer>(M+1);
for(int i = 0; i < N; i++){
    if(pq.size() < M)
        pq.insert(a[i]);
    if(pq.min() <= a[i]){
        pq.insert(a[i]);
        pq.delMin();
    }
}
return pq;

}

Solution

  • The complexity is O(Nlog(M)). The worst case is when the array is sorted in a ascending order, in this case each element is inserted to the queue. The best case is when the array is sorted in a descending order, in this case only the first M elements are inserted. The complexity in the best case is O(N+Mlog(M)). p.s. the first comment is correct, the second if should be else if.