Что такое O(n) в алгоритме

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

Пример:

def linear_search(arr, target):
    for element in arr:  # O(n) — один проход по всем элементам
        if element == target:
            return True
    return False

Нюансы:

1. O(n) считается хорошей сложностью для многих задач
2. Константные множители (например, 2n) в Big O опускаются — всё равно O(n)
3. Если алгоритм имеет несколько последовательных циклов (не вложенных), общая сложность остаётся O(n)