Обяснете концепцията за времева сложност 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).