Kann man erklären, was die zeitliche Komplexität eines Algorithmus von O(n) bedeutet?

Die Laufzeitkomplexität eines Algorithmus, gleich O(n), bedeutet, dass die Ausführungszeit des Algorithmus linear mit der Größe der Eingabedaten n wächst. Wenn sich die Anzahl der Elemente verdoppelt, verdoppelt sich auch die Laufzeit ungefähr.

Zum Beispiel, wenn Sie eine Schleife haben, die alle Elemente eines Arrays mit n Elementen durchläuft, ist dies ein typischer Fall von O(n):

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

Hier hängt die Ausführungszeit direkt von der Anzahl der Elemente im Array ab.