Сложность модифицированного MergeSort

Question

Я хочу посчитать инверсии при сортировке массива с помощью сортировки слиянием. Для этого я добавил переменную в условные выражения, чтобы она увеличивалась при каждом обращении. псевдокод:

mergesort(M, l, r) begin
  if (l < r) then
    int m <- (l + r - 1)/2; //for rounding down I use explicitly int
    inv <- 0; //set number of inversions
    mergesort(M, l, m)
    mergesort(M, m+1, r)
    i <- l;
    j <- m + 1;
    k <- l;
    while(i <= m and j <= r) do
      if (M[i] <= M[j]) then
        M'[k] <- M[i];
        i <- i + 1;
      else 
        M'[k] <- M[j];
        j <- j + 1;
        inv <- inv + 1;  //Counting inversions
      k <- k + 1;
    for (h = i, .. , m) do
      M[k + (h - 1)] <- M[h]; 
    for (h = l, .. , k -1) do
      M[h] <- M'[h];
end.

Однако я не уверен, что сложность остается прежней: O(n log n).

Способствует ли увеличение только одной переменной ухудшению сложности WC? Как я знаю, это зависит только от наибольшего слагаемого (n-фактор). И сильно ли изменит сложность добавление константы или, в худшем случае (n - 1) + (n - 2) = 2n - 3 приращений? Если да, что бы вы предложили?

Answer 1

Если вы посмотрите на эти две строки

    j <- j + 1;
    inv <- inv + 1;  //Counting inversions

Они оба T(1) арифметические операции, они в той же глубине, поэтому T(1)+T(1) = T(1), Дополнительная линия inv <- inv + 1; не может изменить сложность, потому что время выполнения остается неизменным.