Основні класи
- O(1) — константний час. Доступ до масиву за індексом, хеш-таблиця. Не залежить від n
- O(log n) — логарифмічний. Бінарний пошук. Швидко навіть для мільярдів елементів
- O(n) — лінійний. Перебір масиву. Подвоїли n — подвоїли час
- O(n log n) — Merge Sort, QuickSort (середній випадок)
- O(n²) — вкладені цикли. Bubble Sort. Стає непридатним при n > 10000
- O(2ⁿ) — експоненційний. Перебір всіх підмножин. Надто повільний
На практиці
SQL-запит без індексу — O(n). З індексом — O(log n). Саме тому індекси в 100 разів важливіші за оптимізацію PHP-коду.