Mi az összefüggő komplexitás több áthaladás esetén a listán?

Ha van egy n elemű listád, és többször egymás után végigmész rajta (például k alkalommal), akkor az összes aszimptotikus összetettség O(k * n) lesz.

Azonban, ha k egy konstans (állandó számú áthaladás), akkor a komplexitás egyszerűsödik O(n)-re, mivel a konstansokat általában elhagyják az aszimptotikus jelölésben.

Példa: ha kétszer végigmész az n elemű listán, a komplexitás O(2n), ami egyenértékű az O(n)-nel.

Így több egymást követő áthaladás a listán nem változtatja meg a komplexitás növekedési sorrendjét, ha az áthaladások száma nem függ az adatok méretétől.