Объясните концепцию временной сложности O(n) и в каких ситуациях она применяется?

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

Это значит, что если количество элементов в наборе данных удваивается, время выполнения примерно удваивается.

Пример ситуации с O(n):

• Поиск элемента в неотсортированном массиве перебором всех элементов.
• Подсчёт суммы всех чисел в списке.

Пример на Swift:

func sumArray(_ array: [Int]) -> Int {
    var sum = 0
    for num in array {
        sum += num
    }
    return sum
}

Здесь функция проходит по всем элементам массива один раз, поэтому её временная сложность — O(n).