Se poate explica ce înseamnă complexitatea temporară a unui algoritm egală cu O(n)?

Complexitatea temporară a unui algoritm, egală cu O(n), înseamnă că timpul de execuție al algoritmului crește liniar odată cu creșterea dimensiunii datelor de intrare n. Dacă numărul de elemente se dublează, timpul de funcționare se apropie de dublare.

De exemplu, dacă aveți un ciclu care parcurge toate elementele unui array de n elemente, acesta este un caz tipic O(n):

void PrintElements(int[] arr) {
    for (int i = 0; i < arr.Length; i++) {
        Console.WriteLine(arr[i]);
    }
}

Aici, timpul de execuție depinde direct de numărul de elemente din array.