Биг-О нотация Помощь

Question

while (n >= 1)

n /= 2;

Я не могу получить обозначение Big-O для этого

Answer 1

Я просто последую совету Пойнти ради экспозиции.

Попробуйте 8.

4 2 1 0: 4 iterations.

Попробуйте 32.

16 8 4 2 1 0: 6 iterations.

Попробуйте 66.

33 16 8 4 2 1 0: 7 iterations.

Итак ... как меняются начальные числа и как меняется число итераций?

Answer 2

Любой алгоритм, который решает проблему пополам каждый раз, равен O (log (n)).

Answer 3

T (n) = O (log ₂ n)