Gran O:¿Por qué la complejidad temporal de estos bucles es O (N)?

Question

Tengo la siguiente función.

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

Tiene O(N) complejidad del tiempo.Pensé que es O(N LogN)(es decir.Si eliminamos el bucle interior obtenemos)

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

Esto es O(Log N) ¿no es así?Y el bucle interior resulta ser O(N) ya que simplemente aumenta linealmente.Así que creo que se supone que así es O(Log N * N).¿Qué podría salir mal en mi pensamiento?

Answer 1

Mira cuántos pasos está dando el bucle interior.Es $n + \frac{1}{2}n + \frac{1}{4}n + \cdots$.Sin embargo, el series geométricas Cuéntanos:

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