Биг-О:Почему временная сложность этих циклов O(N)?

Question

У меня есть следующая функция.

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

В нем есть O(N) временная сложность.Я думал, что это O(N LogN)(т.е.Если убрать внутренний цикл, то получим)

for (int i = n; i > 0; i /= 2){
...
}

Это O(Log N) не так ли?И внутренний цикл оказывается O(N) поскольку он просто увеличивается линейно.Так что я думаю, что так и должно быть O(Log N * N).Что может пойти не так в моей мысли?

Answer 1

Посмотрите, сколько шагов делает внутренний цикл.Его $n + \frac{1}{2}n + \frac{1}{4}n + \cdots$.Однако геометрическая серия говорит нам:

$$\sum_{k=0}^{\lceil\log n ceil +c}\frac{n}{2^k} < n\sum_{k=0}^\infty \frac{1}{2 ^к} = 2n$$