Какова временная сложность следующего кода

Question

Какова временная сложность следующего кода?Во втором для цикла j увеличивает j = j * 2

`int k=0;
 for(i=1;i<=n;i++)
     for(j=1;j<n;j=j*2)
         k=k+1;
 return k;`

Answer 1

Два цикла независимы, потому что ни один не зависит от другого.Таким образом, мы можем выразить сложность двух вложенных циклов как произведение отдельных сложностей.В этом случае внешний цикл в i равен O(n), а внутренний цикл в j равен O(lgn) (основание журнала 2 из n).Итак, общее время составляет O(nlgn).

Чтобы понять, почему внутренний цикл равен O(lgn), рассмотрим значение n, равное 16:

j  | step#
1  | 1
2  | 2
4  | 3
8  | 4
16 | 5

Мы видим, что оносделал 5 шагов для генерации 16, что примерно равно lg(16).