Почему сложность времени O (n) вместо O (n ^ 2) в этом коде?

Question

Почему здесь сложность времени не O (n ^ 2), а вместо этого O (n)? Разве первый цикл не равен n раз, а тот же самый второй, поэтому он становится O(n*n), что здесь не так?

void f(int n){

     for( ; n>0; n/=2){
         int i;
         for(i=0; i<n; i++){
             printf("hey");
         }
     }
}

Answer 1

Разве первый цикл не n раза, а второй - тот же самый, поэтому он становится O(n*n).

Вышеупомянутое утверждение ложно, так как:

1. Внешний цикл не запускается n раз. (Внешний цикл запускается O(log n) раз, но в данном случае это не имеет значения.)
2. Для внутреннего цикла число циклов отличается при изменении значения n.

Чтобы получить временную сложность этого кода, мы должны подсчитать общее количество раз, которое выполняется тело внутреннего цикла.

1. Очевидно, что тело внутреннего цикла выполняется n раз, для каждого значения n.
2. Значение n определяется оператором for внешнего цикла. Он начинается со значения, данного в качестве аргумента функции, и уменьшается вдвое при каждом выполнении тела внешнего цикла.

Итак, как уже отмечалось в комментариях, начиная с n + n/2 + n/4 + n/8 + ... = 2n, сложность времени для этого алгоритма составляет O(n).

---

Для более конкретного математического доказательства:

Найдите целое число k такое, что 2^(k-1) < n <= 2^k. Для этого k:

1. Нижняя граница для общего числа внутренних циклов составляет 1 + 2 + 4 + ... + 2^(k-1) = 2^k - 1 >= n - 1 ∈ Ω(n).
2. Верхняя граница для общего количества внутренних циклов: 1 + 2 + 4 + ... + 2^k = 2^(k+1) - 1 < 4n - 1 ∈ O(n).

Поэтому общее количество внутренних циклов равно Θ(n), а также O(n).