Big-o: perché la complessità del tempo è di questi loop o (n)?

Question

Ho la seguente funzione.

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

.

ha la complessità del tempo di O(N).Pensavo che sia O(N LogN) (cioè se rimuovi il loop interno otteniamo)

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

.

Questo è O(Log N) non è vero?E il ciclo interno risulta essere O(N) mentre aumenta semplicemente linearmente.Quindi penso che dovrebbe essere O(Log N * N).Cosa potrebbe andare storto sul mio pensiero?

Answer 1

Guarda quanti passi sta prendendo il loop interno.È $ n + \ frac {1} {2} n + \ frac {1} {4} n + \ cdots $ .Comunque Geometric Series ci dice:

$$ \ sum_ {k= 0} ^ {\ lceil \ log n \ rceil + c} \ frac {n} {2 ^ k}