Временная сложность простого цикла

Question

Меня смущает сложность этого кода во времени.

int a = 1;

while ( a < n ) {
  a = a * 2;
}

Я новичок в сложности времени

Answer 1

Если вы проверите значения a, которые вы можете получить, вы увидите:

1, 2, 4, 8, 16, 32, ..., 

и итерации будут продолжаться до тех пор, пока a не станет меньше n, что означает, что количество итераций ограничен ⌈log2(n)⌉.

Таким образом, вы можете сделать вывод, что сложность времени логарифмическая c в n.

Answer 2

Это журнал (n). Если n равно 4, l oop выполняется 2 раза. Если n равно 8, l oop выполняется 3 раза. Если n равно 16, l oop выполняется 4 раза.

Это логарифмическое отношение c, а не линейное.