Временная сложность зависимого вложенного логарифмического цикла - PullRequest
Новая
       8

Временная сложность зависимого вложенного логарифмического цикла

1 голос
/ 13 марта 2019

Какова сложность Big-O следующего цикла? 

for (int i=2; i <= n; i=i*2) {
    for (int k=i; k <= n; k=k*2) {
        times++;
    }
}

Внешний цикл, конечно, логарифмический, но я не уверен, как справиться с растущим начальным условием второго цикла,Это похоже на логарифмическую сложность, но как мне получить k = i там?

...