Сложность - бигтета 3 за цикл

Question

Я просто решаю проблему, но у меня нет решения этой проблемы, поэтому я прошу вас подтвердить, правильно ли мое решение или нет.

int h=1; int cont = 0;

for (j = 2^N; j>1; j = j/2) {
        h = h * 2;
        for (i =1; i < j; i = i*2)
           for (k=2; k<h; k++)
               cont ++;
}

Я должен найти сложность этой части кода в BIGTHETA.

Итак, я анализирую, что таким образом растет третий цикл

k -> линейный до = h (h растут как 2^w) - таким образом, сложность log n.

Что касается второго, предел первого цикла равен 0, так что я думаю, что сложность равна log n.

О первых 2^N = 2^N-1, поэтому сложность составляет п

Общая сложность n * log n

Answer 1

Вы можете действовать формально, шаг за шагом, используя сигма-нотацию (я пропустил некоторые шаги, но не стесняйтесь спрашивать более подробную информацию, если это необходимо):