Létezhet O (1) legjobb eset futásidejű rendezés?

Ahhoz hogy rendezni tudj, minimum egyszer végig kell menned az elemeken legalább azért hogy megtudd mondani hogy alapból rendezett e, de az már O(n). Bogosort sem O(1), még a legjobb esetben sem. Az elméleti legjobb összehasonlítás alapú rendezés O(n*logn), a nem összehasonlítás alapú pedig O(n).

O(1)-ről legfeljebb akkor beszélhetnénk ha lenne egy olyan elméletbeli kvantum számítógépünk ami végtelen-számú állapot megkülönböztetésére képest. Ez nyilván lehetetlen.

@TXCowboy:

Tehát szerinted ha végigmész n elemen egyszer (és elhelyezed őket egy tömbben) akkor az nem O(n) lépés hanem O(1)? Gratulálok. Csak 1 kommentet kellett volna visszaolvasnod.