Асимптотическая оценка для целочисленного деления

Question

k = n; //integer division
while(k > 1) {
    std::cout << k; 
    k=k/2;
}

Мне нужно выяснить асимптотическую оценку как функцию от n.

Answer 1

Сложность логарифмическая.

Предполагая, что K неотрицательно, деление на два эквивалентно сдвигу вправо на один бит. Поэтому максимальное количество итераций до k становится 0 это количество бит в k, Более конкретно, позиция самого значительного бита в k что установлено (т.е. 1) определит количество итераций, выполненных в цикле.

Поскольку операции в цикле (предположительно) имеют постоянную сложность, логарифмическое число итераций приводит непосредственно к логарифмической сложности.