Jaká je asymptotická složitost při několika průchodech seznamem?

Pokud máte seznam s n prvky a procházíte jím několikrát po sobě (například kkrát), celková asymptotická složitost bude O(k * n).

Pokud je však k konstantní (pevný počet průchodů), složitost se zjednodušuje na O(n), protože konstanty se obvykle v asymptotické notaci vynechávají.

Příklad: pokud projdete seznam s n prvky dvakrát, bude složitost O(2n), což je ekvivalentní s O(n).

Tím pádem několik po sobě jdoucích průchodů seznamem nemění řád růstu složitosti, pokud počet průchodů nezávisí na velikosti dat.