Wie schreibt man die algorithmische Komplexität? Wie ist die Komplexität des Bubble-Sortings? Wie ist die Komplexität des Quicksort?

Die algorithmische Komplexität wird üblicherweise in der Big-O-Notation geschrieben, die die asymptotische Schätzung der Laufzeit oder des Speicherverbrauchs des Algorithmus in Abhängigkeit von der Größe der Eingabedaten beschreibt.

• Bubblesort hat im schlimmsten und durchschnittlichen Fall eine Komplexität von O(n²), da jedes Element mit jedem verglichen wird.

• Quicksort arbeitet im Durchschnitt in O(n log n), kann im schlimmsten Fall (z.B. wenn das Array bereits sortiert ist und ein schlechter Pivot gewählt wird) auf O(n²) verschlechtern.

Beispiel für die Schreibweise:

Bubblesort: O(n^2)
Quicksort: O(n log n) im Durchschnitt, O(n^2) im schlimmsten Fall