Hacker News Digest

Big O — способ описать, как время работы функции растёт с ростом входных данных, без привязки к конкретным секундам.

Рассмотрим 4 основные категории:

---

O(n) — линейное время

function sum(n) {
  let total = 0;
  for (let i = 1; i <= n; i++) total += i;
  return total;
}

• sum(1e9) ≈ 1 с
• sum(2e9) ≈ 2 с
  Время пропорционально n.

---

O(1) — константное время

function sum(n) {
  return (n * (n + 1)) / 2;
}

• sum(1e9) и sum(100e9) выполняются почти мгновенно.
  Время не зависит от n.

---

Ключевые идеи

• O = «order of growth»; описывает рост, а не абсолютное время.
• O(1) ≠ «быстро», а «не растёт с размером входа».
• При достаточно большом n O(1) всегда обгонит O(n).