Объясните O (N) временную сложность алгоритма

Question

Может кто-нибудь объяснить сложность времени O (N) для следующего алгоритма:

int count = 0;
for (int i = N; i > 0; i /= 2) {
    for (int j = 0; j < i; j++) {
        count += 1;
    }
}

Answer 1

Количество приращений count равно N+N/2+N/4+N/8+...<2N

Answer 2

Если вы рекурсивно оцените сложность времени, у вас будет T(n) = T(n/2) + n. Используя основную теорему, вы можете получить результат, как c = log_2(1) = 0 и n = \Omega(n^c) (третий случай основной теоремы). Следовательно, T(n) = \Theta(n) или T(n) = O(n).