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

Сколько раз нужно поделить $n$ на два нацело, чтобы получить единицу?

Это и есть тот самый логарифм из оценки $O(n \log n)$ — полезно увидеть, насколько он маленький.

Одно число $n$ от $1$ до $10^{18}$.

Одно число.

У чисел до $10^{18}$ ответ не превосходит 59. Поэтому множитель $\log n$ в оценке почти никогда не решает: между $O(n)$ и $O(n \log n)$ разница в несколько десятков раз, а между $O(n)$ и $O(n^2)$ — в сотни тысяч.