Сложность времени итерационного алгоритма?

Question

Это алгоритм: Я думаю, что его время сложность O (NlogN), но я не уверен,

k=1; 
while (k<=n) do  
    j=1; 
    while (j<=k) do   
     sum=sum+1; 
     j=j+1; 
    k=k*2; 

Answer 1

Внутренний цикл в первый раз выполняет итерацию 1, на вторые 2 итераций. Последовательность выглядит как 1, 2, 4, 8, 16, 32, ... до тех пор, пока она меньше или равна n. Последовательность может содержать Θ(log(n)) элементов, но ее сумма равна Θ(n). Это происходит потому, что

1 + 2 + 4 + ... + 2^к = 2 * 2^к - 1

и мы знаем n/2 < 2^k <= n. Таким образом, внутренний цикл выполняется Θ(n) раз , и для выполнения каждого внутреннего цикла требуется постоянное количество инструкций.

Остальная часть кода просто log(n) присвоений j = 1 и log(n) двойники k.

Таким образом, временная сложность алгоритма Θ(n).

Answer 2

// code     | max times executed 
k=1;     | 1 
while (k<=n) do   | log n 
    j=1;    | log n 
    while (j<=k) do  | log n * n 
     sum=sum+1;  | log n * n 
     j=j+1;   | log n * n 
    k=k*2;    | log n 

Таким образом, сложность O представляется n log n.