Wat is de asymptotische complexiteit bij meerdere doorlopen van de lijst?

Als je een lijst hebt van n elementen en je doorloopt deze meerdere keren achter elkaar (bijvoorbeeld k keer), dan is de totale asymptotische complexiteit O(k * n).

Als k echter een constante is (een vast aantal doorlopen), wordt de complexiteit vereenvoudigd tot O(n), omdat constanten meestal worden weggelaten in de asymptotische notatie.

Voorbeeld: als je de lijst van n elementen twee keer doorloopt, is de complexiteit O(2n), wat gelijk is aan O(n).

Dus, meerdere opeenvolgende doorlopen van de lijst veranderen de groeiregel van de complexiteit niet, als het aantal doorlopen niet afhankelijk is van de gegevensgrootte.