Рассматривая O (log (N)) для сложности времени, на чем основывается log?
Все логарифмы связаны некоторой константой. (Отсюда формула смены базы ). Поскольку мы обычно игнорируем константы при анализе сложности, база не имеет значения.
Обычно при создании алгоритма основание считается равным 2. Рассмотрим сортировку типа сортировка слиянием . Из него можно построить дерево , а высота дерева log₂ n, потому что каждый узел имеет две ветви.
log₂ n
Неважно, относительная сложность одинакова независимо от используемой базы.
Один способ думать об этом - это O (log 2 X) = O (log 10 X) = O (log N X)