La complessità del tempo di fun()?

Question

Stavo passando questa domanda per calcolare la complessità del tempo.

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

La mia prima impressione è stata O (n log n), ma la risposta è O (n). Per favore aiutami a capire perché è O (n).

Answer 1

Il ciclo interno fa n iterazioni, poi n/2, poi n/4, ecc Quindi il numero totale di iterazioni del ciclo interno è:

n + n/2 + n/4 + n/8 + ... + 1 
<= n * (1 + 1/2 + 1/4 + 1/8 + ...) 
= 2n 

(Vedere Geometric series), e quindi è O (n).