Какая сложность у такого цикла for?

Question

[undying234]

...
for(unsigned int i = 1; i<N;i<<=1){
    ...какие-то вычисления
}
...

Я очень плохо разбираюсь в оценке сложности, но мне кажется его сложность будет O(logN). Так ли это? И если нет, то какая его сложность?

Answer 1

[Wataru]

Так.

Answer 2

[wisgest]

Да. Цикл выполнится столько раз, сколько значащих двоичных цифр в N. Количество цифр в записи натурального числа N без возможных незначащих ведущих нулей приблизительно равно его логарифму (целая часть логарифма N+1 по основанию системы счисления).