Grande-O:Por que a complexidade de tempo desses loops é O(N)?

Question

Eu tenho a seguinte função.

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; 
} 

Tem O(N) complexidade do tempo.Eu pensei que é O(N LogN)(ou seja,Se removermos o loop interno, obtemos)

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

Isso é O(Log N) não é?E o loop interno acaba sendo O(N) pois apenas aumenta linearmente.Então eu acho que deveria ser O(Log N * N).O que pode dar errado no meu pensamento?

Answer 1

Veja quantas etapas o loop interno está dando.Isso é $n + \frac{1}{2}n + \frac{1}{4}n + \cdots$.No entanto, o Séries geométricas diga-nos:

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