Złożoność czasu zabawy()?

Question

Przejrzałem to pytanie, aby obliczyć złożoność czasu.

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

Moje pierwsze wrażenie było O (n log n), ale odpowiedź jest O (n). Pomóż mi zrozumieć, dlaczego jest to O (n).

Answer 1

Wewnętrzna pętla ma n iteracji, następnie n/2, następnie n/4 itp Sumaryczna liczba iteracji pętli wewnętrznej to:

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

(Patrz Geometric series) i dlatego jest O (n).