Welke methoden worden gebruikt om de efficiëntie en complexiteit van een algoritme te bepalen?

De efficiëntie en complexiteit van een algoritme worden meestal beoordeeld door middel van analyse van de tijd- en ruimtecomplexiteit.

• Tijdcomplexiteit toont hoe de uitvoeringstijd van het algoritme afhankelijk is van de grootte van de invoergegevens. Dit wordt meestal uitgedrukt in de notatie "Big O", bijvoorbeeld O(n), O(n²), O(log n).
• Ruimtecomplexiteit geeft weer hoeveel geheugen het algoritme nodig heeft afhankelijk van de grootte van de invoergegevens.

Om de complexiteit te bepalen, wordt het aantal hoofdoperaties (bijvoorbeeld vergelijkingen, toewijzingen) geanalyseerd in het slechtste, gemiddelde en beste geval.

Voorbeeld: de bubble sort heeft een tijdcomplexiteit van O(n²), omdat in het slechtste geval ongeveer n² vergelijkingen nodig zijn.

Ook kan de efficiëntie empirisch worden gemeten door het algoritme uit te voeren met verschillende datavolumes en de tijd en het geheugengebruik te meten.