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

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

Пример:

function findElement(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) return i;
  }
  return -1;
}

В худшем случае (элемент отсутствует) алгоритм выполнит n операций, где n — длина массива. График такой зависимости — прямая линия.

Ключевые особенности:

• Время выполнения прямо зависит от размера данных
• Типично для простых циклов по массивам/спискам
• Считается "хорошей" сложностью для многих задач