Как проанализировать рост следующего кода?

Question

Я уже знаю, что сложность в худшем случае равна N, а в лучшем случае - Mlog (M), но я просто не понимаю, как это сделать.Кто-нибудь может объяснить мне, почему это так, и какие разные входные данные будут вызывать каждый случай?

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;

}

Answer 1

Сложность O(Nlog(M)). В худшем случае, когда массив сортируется в порядке возрастания, в этом случае каждый элемент вставляется в очередь. В лучшем случае, когда массив сортируется в порядке убывания, в этом случае вставляются только первые М элементов. Сложность в лучшем случае составляет O(N+Mlog(M)). постскриптум первый комментарий правильный, второй if должен быть else if.