временная сложность вложенного цикла цикла с j <= i условие

Question

У меня был этот вопрос по заданию.

Определить временную сложность вложенного цикла

for(int i=1; i<=n; i=2*i){ 
    for(int j=1; j<=i; i=2*j){ 
     stuff 
    } 
} 

Я понимаю, что с я и J инкрементируется в 2 раза, что сложность будет что-то вдоль линий log2 (п) * log2 (п) , но с внутренней петлей, идущей на i, а не с n. Я полностью потерял

Мне нужно знать сложность вложенного цикла и шаг за шагом о том, как он был решен.

Answer 1

Внутренний цикл работает log(i) + 1 раз (база базы 2).

Добавление внешней петли, суммой выше для i = 1, 2, 4, ... n.

Итак: (log(1) + 1) + (log(2) + 1) + (log(4) + 1) + ... + (log(n) + 1)

который: 1 + 2 + 3 + ... + log(n)

использованием суммы арифметической серии: (log(n) + 1) * (log(n) + 2)/2 = (log(n)*log(n) + 3log(n) + 2)/2 = O(log(n) * log(n))

Answer 2

Предположим, п = 16, например, так что я буду иметь значения i = 1, 2, 4, 8, 16.

Итак: i в основном принимает значение как log (n) i.e log (16), то есть пять итераций.

теперь для значения j, оно принимает значение как log(1) + log(2) + log(4) + log(8) + log(16). Это в основном равно log (i) на каждой итерации.

Таким образом, комбинируя значения, полученные нами из вышеуказанных двух утверждений, можно сказать, что сложность времени приведенного выше кода равна O(log(n) * log(i)).

Это мое понимание о коде.