Как доказать алгоритм Θ (log n), используя нотацию суммирования?

Question

Предположим, у меня есть следующий код:

int sum = 0; 
int val=128; 
for (int i=n; i>=1; i=i/2) { 
    for (int j=1; j<val; j++) { 
    sum ++; 
    } 
} 

Как бы вы доказать, что это будет Θ (журнал N) математически?

Моим обычным подходом было бы использовать суммирование (сигма-нотация), но в этом случае мы не увеличиваем линейную переменную цикла. Какой хороший подход для этого?

Answer 1

Значения i: n, n/2, n/4, ..., 1. Поскольку это целое число, его конечное значение равно 1 с этим условием. Предположим, что n будет 2^k, тогда число итераций будет k, что равно log n. Поэтому ситуация не меняется, это еще один for с определенным количеством итераций.

Внутренний цикл можно рассматривать как один оператор, поскольку val является постоянным.