«O» означает «не хуже, чем».
Если вы говорите, что алгоритм работает за O(n), это значит, что в худшем случае время выполнения не превысит линейное (n). (Технически это математическое обозначение для верхней границы).
Вытаскивание значения из БД по индексу - от О(1) до О(log(n)). Потому что:
Большинство баз данных по умолчанию используют B-Tree(а он О(log(n)), потому что он универсален. Но если ваша задача — "достать запись по ID" и больше ничего, HASH-индекс может ускорить этот процесс в разы на больших объемах данных.
HASH-индекс это тоже Индекс, но другой.
Один цикл for по массиву — это O(n).
Два вложенных цикла (for внутри for) — это O(n²).
Три вложенных — это O(n³).
----------------
Big O («Большое О»)» — это математическая нотация, которая в программировании и IT используется для описания асимптотической сложности алгоритмов.
Асимптотический анализ алгоритмов
Простыми словами: это способ измерить, как сильно вырастет время выполнения (или потребление памяти) алгоритма, когда размер входных данных (N) становится очень большим.
Главная задача Big O — не посчитать точные секунды (это зависит от железа), а понять, насколько быстро алгоритм «тормозит» при росте данных.