Hoe wordt de algoritmische complexiteit geschreven? Wat is de complexiteit van bubble sort? Wat is de complexiteit van quicksort?

De algoritmische complexiteit wordt gewoonlijk uitgedrukt in Big O-notatie, die de asymptotische schatting beschrijft van de uitvoeringstijd of het geheugenverbruik van het algoritme afhankelijk van de grootte van de invoergegevens.

• Bubble sort heeft een complexiteit van O(n²) in het slechtste en gemiddelde geval, omdat elk element met elk ander wordt vergeleken.

• Quick sort werkt gemiddeld op O(n log n), maar kan in het slechtste geval (bijvoorbeeld wanneer de array al gesorteerd is en een slecht pivot wordt gekozen) degraderen tot O(n²).

Voorbeeld van notatie:

Bubble sort: O(n^2)
Quick sort: O(n log n) gemiddeld, O(n^2) in het slechtste geval