Почему следующий код имеет сложность O (n)?

Question

У меня была проблема с практикой на этой странице .Вопрос требует сложности времени для приведенного ниже кода, и ответ O (n).Однако, как я понимаю, внешний цикл запускает log (n) раз, а внутренний - O (n), поэтому он должен иметь сложность O (n * log (n)).

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

Пожалуйста, уточните, чтоя здесь скучаю.

Answer 1

Внутренний оператор выполняется N + N / 2 + N / 4 + N / 8 + ... раз.Что равно 2 * N = O (N).