Почему этот фрагмент O (n)?

Question

Предполагается, что этот фрагмент кода имеет сложность O(n).Тем не менее, я не понимаю, почему.

sum = 0;
for (k = 1; k <= n; k *= 2)  // For some arbitrary n
  for (j = 1; j <= k; j++)
    sum++;

Теперь я понимаю, что внешний цикл сам по себе равен O(log n), поэтому почему добавление внутреннего цикла делает это O(n).

Answer 1

Пусть m = floor(lg(n)).Тогда 2^m = C*n с 1 <= C < 2.Число k шагов во внутреннем цикле выглядит следующим образом:

1, 2, 4, 8, ..., 2^m = 2^0, 2^1, ..., 2^m

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

2^0 + 2^1 + ... + 2^m = 2^{m+1} - 1      ; think binary
                      = 2*2^m - 1
                      = 2*C*n - 1        ; replace
                      = O(n)

Answer 2

Предположим, что n является степенью 2 на момент.

Последняя итерация внутреннего цикла будет выполняться n раз.Итерация до этого будет выполняться n / 2 раза, вторая до последней итерации n / 4 раза и так далее до первой итерации, которая будет выполняться один раз.Это формирует ряд, который суммирует 2 n - 1 всего итераций.Это O ( n ).

(Например, при n = 16 внутренний цикл выполняется 1 + 2 + 4 + 8 + 16 = 31 всегораз.)