Логарифмическая.
Сравнение сложностей:
| Сложность | Описание | Пример алгоритма |
|---|---|---|
O(\log n) | Время выполнения растет медленно с увеличением n. | Бинарный поиск |
O(n) | Время выполнения растет пропорционально n. | Проход по списку |
При n > 2, \log n < n.
Пример сравнения при n = 1000:
\log_2 1000 \approx 101000python