Сложность времени для следующего алгоритма?

Question

Я сейчас обучение Big-O нотации и наткнулся на этот небольшой алгоритм в другом потоке:

i = n 
while (i >= 1) 
{ 
    for j = 1 to i // NOTE: i instead of n here! 
    { 
     x = x + 1 
    } 
    i = i/2 
} 

Согласно автору поста, его сложность Θ (п), но я не могу выяснить как. Я думаю, что сложность цикла while равна Θ (log (n)). Сложность цикла for из того, что я думал, также будет Θ (log (n)), поскольку количество итераций будет уменьшаться в два раза каждый раз.

Итак, не будет ли сложность всего этого Θ (log (n) * log (n)), или я делаю что-то неправильно?

Edit: сегмент в лучшем ответе этого вопроса: https://stackoverflow.com/questions/9556782/find-theta-notation-of-the-following-while-loop#=

Answer 1

Представьте себе для простоты, что n = 2^k. Сколько раз x получает приращение? Отсюда легко это Geometric series

2^к + 2^(к - 1) + 2^(к - 2) + ... + 1 = 2^(к + 1) - 1 = 2 * n - 1

Так что эта часть Θ(n). Также i get's halfved k = log n раз, и он не имеет асимптотического эффекта до Θ(n).

Answer 2

Значение i для каждой итерации while цикла, который также, сколько итераций цикла for имеет, является п, п/2, n/4, ..., а общая сложность - это сумма. Это ставит его примерно в 2n, что дает вам вашу Theta (n).