Waarom is dit belangrijk?
Weten hoe snel een berekening groeit, maakt het mogelijk een aanpak te kiezen die bij meer gegevens op tijd klaar is. In de zorg gaat het dan om patiënten aan bedden koppelen, en in het onderwijs om lesroosters zonder overlappende vakken. Medewerkers en studenten hebben een planning nodig die op tijd af is, maar een zware methode kan bij veel gegevens zo traag worden dat de uitkomst te laat komt.
Zo werkt het in de praktijk
Zoekalgoritmen voor tekst, zoals Boyer-Moore en Ukkonen, werken met lineaire tijdscomplexiteit. Binair zoeken in een gesorteerde lijst blijft logaritmisch, en lineair zoeken kan elk element aflopen. In cryptografie houden ontwerpers de tijdscomplexiteit soms constant, tegen aanvallen via tijdmeting.
Onderzoek zoekt lineaire of bijna lineaire tijd als het programma alle invoer leest. Klasse P bevat ja-nee-vragen waarvan de tijd als een macht van de invoer groeit. Vergelijkend sorteren heeft in het slechtste geval minstens n log n vergelijkingen.
Donald Knuth gaf de werkwijze de naam analyse van algoritmen. Big-O-notatie geeft daarin een bovengrens voor de groei van het aantal stappen. Het uniforme kostenmodel rekent met vaste kost per stap en het logaritmische laat de kost meegroeien met het aantal bits.




