Sortowanie w czasie O(N)

Sortujac n elementow porownujac je ze soba ile z nich mozna posortowac w czasie O(N) ? wedlug mnie 3 ale sa tacy ktorzy twierdza ze 4. Czy ktos moze to rozstrzygnac prosze?

W czasie O(N) (a nawet O(1)) można posortować każdą dowolną SKOŃCZONĄ USTALONĄ liczbę elementów.

Gdy N skończone i ustalone, to O(2^N) == O(N) == O(1).
np. dla N==5: O(2^{N) == O(2}5) == O(32) == O(1)

Więc jeżeli masz dane o skończonym ustalonym rozmiarze, to posortujesz je w czasie O(1) nawet algorytmem o złożoności asymptotycznej O(N^NN^N)

Nie bardzo rozumiem Porownujac elementy ze soba w czasie sortowania jak mozna uzyskac O(1) sortujac je w ten sposob? Majac np 2 liczby mozemy je posortowac porownujac je ze soba w czasie O(1) majac 3 liczby porownujemy dwie pierwsze i z posortowana para porownujemy trzecia Kazda nastepna operacja bedzie juz w czasie albo O(n^2) albo O(n logn) Kazdy logarytm sortowania oparty na porownywaniu elementow dziala w czasie O(n log n) chyba ze liczba elementow jest 2 atedy sortowanie odbywa sie w czasie O(1) i dodajac do tego jeszcze jeden element mamy juz O(n) wszystko powyzej tego wydaje mi sie ze bedzie juz O(n log n )

N porównań to co innego niż O(N) porównań

O(332432) == O(1)
Ale 332432 != 1

O(N) == O(1) dla N ustalonego
O(1) zawiera się w O(N), ale O(1) != O(N) dla N nieustalonego

http://en.wikipedia.org/wiki/Big_O_notation sekcja "Formal definition"

No dobrze, nie będę się nad tobą pastwił i napiszę to, o co ci chodziło

N porównania
3 - 3
4 - 5
5 - 7