Что быстрее O(n) или O(log(n))

O(log(n)) быстрее O(n).

Почему?

• O(n) означает, что время выполнения растёт линейно с размером входных данных.
• O(log(n)) — логарифмическая сложность, время растёт гораздо медленнее.

Пример:
Для n = 1_000_000:

• O(n) → ~1_000_000 операций.
• O(log(n)) → ~20 операций (логарифм по основанию 2).

Код для сравнения:

import math

n = 1_000_000
print(f"O(n): {n} steps")        # 1,000,000
print(f"O(log n): {math.log2(n):.1f} steps")  # ~19.9

Логарифмические алгоритмы (например, бинарный поиск) эффективнее линейных (например, простой перебор).