Анализ сложности времени для цикла:

Question

Почему сложность времени O(n) вместо O(nlogn)? Разве вам не нужно умножать сложность внешнего цикла на сложность внутреннего цикла?

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

Answer 1

В первой итерации цикла внутренний цикл покрывает половину n. Следующая итерация охватывает четверть, затем восьмую и так далее. Вы можете представить коэффициенты с помощью функции ниже. Как видите, это бесконечный ряд, который суммирует в один. Таким образом, вся функция O(n)