Что такое оценка сложности O(n)

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

Что означает

Если вход увеличить в 2 раза, время выполнения тоже увеличится примерно в 2 раза. Один проход по данным.

// O(n) — один цикл по массиву
function sum(arr) {
  let total = 0;
  for (const x of arr) {  // n итераций
    total += x;
  }
  return total;
}

Нотация O большое

O(n) описывает асимптотический рост при больших n, отбрасывая константы и младшие члены. O(2n) и O(n + 5) — это всё O(n).

Классы сложности для сравнения

• O(1) — константа (доступ по индексу).
• O(log n) — логарифм (бинарный поиск).
• O(n) — линейная (один проход).
• O(n log n) — эффективные сортировки.
• O(n²) — вложенные циклы.

Примеры O(n)

Линейный поиск, суммирование, map, filter, forEach, один for по данным.

Коротко для собеседования

O(n) — линейная сложность: время растёт пропорционально размеру входа (один проход по данным). Нотация O отбрасывает константы (O(2n) = O(n)). Между O(1)/O(log n) (быстрее) и O(n²) (медленнее). Примеры — линейный поиск, map, filter.