Что означает обозначение O (n) в контексте алгоритмов?

Обозначение O(n) в контексте алгоритмов означает линейную временную сложность. 12

Это означает, что время выполнения алгоритма растёт линейно с увеличением размера входных данных. 2 Другими словами, если увеличить размер входных данных вдвое, то время выполнения алгоритма также увеличится примерно вдвое. 2 Если увеличить размер данных в 10 раз, то время выполнения увеличится приблизительно в 10 раз, и так далее. 2

Линейный рост характерен для алгоритмов, которые выполняют постоянное количество операций для каждого элемента входных данных. 2

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