Big-O временная сложность вложенного цикла

Question

Может кто-нибудь сказать мне, что такое временная сложность следующего вложенного цикла:

 for(i=1;i<n;i+=i)
 {
    for(j=1;j<n;j*=j)
       //O(1)
 }

По мне, это будет O (log (n) * log (log (n)) Поскольку внешний цикл будет выполняться log (n) раз, так как мы эффективно умножаем i на 2 на каждой итерации. А во внутреннем цикле мы возводим в квадрат счетчик цикла j на каждой итерации. Итак, последняя сложность - это произведение этих двух. Это правильно или есть какой-то другой ответ. Заранее спасибо: D

Answer 1

Да, сложность O(log2(n) * log2(log2(n))).

Индекс j внутреннего цикла соответствует рекуррентному соотношению j(k) = j(k-1)^2, то есть j(k) = j(0)^(2^k) (доказательство по индукции). Предположим, что j(0) = 2 (не 1, потому что в противном случае вы бы зациклились бесконечно).

Следовательно, число итераций k внутреннего цикла проверяет

    j(k) >= n
<=> 2^(2^k) >= n
 => k >= log2(log2(n))

Число итераций внешнего цикла>> log2(n).