Что такое сложность по памяти для алгоримта на примере O(n)

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

Пример с O(1) (константная память):

def sum_numbers(n):
    total = 0
    for i in range(n):
        total += i
    return total

Здесь используется фиксированное количество переменных независимо от n.

Пример с O(n) (линейная память):

def create_list(n):
    result = []
    for i in range(n):
        result.append(i)
    return result

Здесь память растёт пропорционально n, так как создаётся список размера n.