Объясните, что означает использование памяти O(n) в контексте анализа алгоритмов на примере.

Использование памяти O(n) означает, что объем используемой памяти растет линейно с размером входных данных n.

Например, если у вас есть функция, которая копирует список из n элементов в новый список, то она будет использовать память пропорционально n:

def copy_list(lst):
    new_lst = []
    for item in lst:
        new_lst.append(item)
    return new_lst

Здесь для хранения нового списка выделяется память, равная количеству элементов входного списка. Если входной список удвоится, то и используемая память примерно удвоится.

В отличие от этого, алгоритм с использованием O(1) памяти будет использовать фиксированный объем памяти, не зависящий от размера входных данных.