Сложность определяют по структуре кода — главное, сколько раз выполняются операции относительно n.
Один проход по данным — O(n):
for (let i = 0; i < n; i++) { // одна операция на элемент }
Вложенные циклы по n — O(n²): для каждого из n элементов снова n операций, итого n·n:
for (let i = 0; i < n; i++) { for (let j = 0; j < n; j++) { // n*n операций } }
Деление задачи пополам на каждом шаге — O(log n): чтобы дойти от n до 1, делений нужно примерно log₂n. Для миллиона это всего около 20 шагов.
Правила оценки: константы отбрасывают (O(2n) = O(n)); из суммы берут самое тяжёлое слагаемое (O(n² + n) = O(n²)); обычно считают худший случай. Кроме времени оценивают и память — сколько дополнительного места нужно алгоритму (пространственная сложность).