Сложность времени fun()?

Question

Я рассматривал этот вопрос, чтобы рассчитать сложность времени.

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

Мое первое впечатление было O (п § п), но ответ O (п). Пожалуйста, помогите мне понять, почему это O (n).

Answer 1

Внутренний цикл делает n итераций, затем n/2, то n/4 и т.д. Таким образом, общее число итераций внутреннего цикла:

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

(см Geometric series), и, следовательно, представляет собой О (п).