Как правильно оценить сложность алгоритма O(n)?
f(x) = O(g(x)) при x→y — это так называемый символ Ландау.
И означает, что при x, достаточно близких к y, f(x)

Отсюда же запись O(log n) — ведь разные логарифмы отличаются на константу, которую символы Ландау съедают.

Чем символы Ландау интересны программистам?
1. Кэшами, быстрым процессором, «хитрым» программированием и прочим на больших наборах данных можно выиграть, например, в разы. Порядком сложности алгоритма — намного, намного больше.
2. Пока закон Мура действовал, объёмы данных росли экспоненциально — так что быстро доходило до того, что программу начинали использовать на наборах данных, для которых она просто не предназначалась.
3. Практически приемлемые алгоритмы обычно имеют небольшую сложность — например, до O(n³). И, например, линейный алгоритм за приемлемое время обработает миллионы элементов, n log n — сотни тысяч, n² — тысячи, n³ — сотни.
4. Программисты отлаживают на небольших наборах данных, которые можно обработать вручную. Так что разница между отладочными и боевыми данными бывает большая — а значит, порядок сложности должен влиять сильнее, чем остальные факторы.
Читай определение О-большого.