Нашли ошибку?

Сколько раз делим пополам

ЛёгкаяОценка сложностиГлава 3
Нашли ошибку?

#стек вызовов#O-большоеid: ga-halving-complexity

Функция считает, сколько раз число n можно разделить пополам нацело, пока не останется 1. Определите время её выполнения в зависимости от n.

Пример

halvings(20) → 4: 20 → 10 → 5 → 2 → 1.

Код

def halvings(n: int) -> int:
    if n <= 1:
        return 0
    return 1 + halvings(n // 2)

Какое время выполнения?