Какова сложность времени выполнения этого цикла for

Question

for (int p = t; p > 0; p >>= 1) {
    for (int i = 0; i < n - p; ++i) {
        if ((i & p) != 0) {
            sort2(a, i, i+p);
        }
    }
    for(int q = t; q > p; q >>= 1) {
        for(int i = 0; i < n- q; ++i) {
            if ((i & p) != 0) {
                sort2(a, i+p, i+q);
            }
        }
    }
}

Здесь n - некоторое положительное целое число, а t больше n/2, но не равно n.

. Насколько я понимаю, внутренний цикл for работает для(n-p) раз, но я не мог понять внешний цикл for.

Я попытался найти его следующим образом:

Если t=64 и n=100, он принимает двоичное значение p, равное 64 и, таким образом, p=1000000 base 2 .

Я понимаю, что каждый раз он уменьшается на одну цифру и в этом случае выполняется в общей сложности 7 раз.Я как-то не мог понять общее время.

Кроме того, я понимаю, что третий цикл for, то есть

for(int q = t; q > p; q >>= 1)

вообще не выполняется, поскольку условие q>p не удовлетворяет как p=q=t.

Это правильно?Я только начинаю с алгоритмов.

Answer 1

Для этого: Сложность будет BigO( log(t)(n-t)log(t) )

Исключая сложность функции sort2 внутри цикла for.

Объяснение:

• Сложность внешнего цикла будет равна log(p)+1 [Каждый раз, когда бит смещается вправо на 1 и идет на greater than 0], поэтому при t = 64 цикл будет выглядеть как [64,32, 16, 8, 4, 2, 1].
• Сложность внутреннего цикла будет greater of ( O(n-p), O((n-t)log(t)) )

Выполнение

для второго внутреннего цикла, вложенного в цикл с самым внешним циклом: