liniowość radix sort

[Dumel]

dlaczego wszedzie sie pisze ze radix_sort działa w czasie liniowym? przecież dla n k-cyfrowych liczb to jest jak jakby k razy counting_sort(\(\displaystyle{ \Omega(n)}\)), a poniewaz \(\displaystyle{ k=\Omega(logn)}\) wiec na moje oko zlozonosc tego algorytmu wynosi \(\displaystyle{ \Omega(nlogn)}\)

[argv]

Idąc za Cormenem:
Radixsort jest liniowe jeśli:
- liczba cyfr czyli d jest stała
- liczba mozliwych wartosci przyjmowanych przez cyfre k = O(n)

Więc jeśli liczba cyfr jest stała to robimy d przebiegów po O(n+k) każdy. k = O(n), więc każdy przebieg kosztuje nas O(n), więc d przebiegów to d*O(n) czyli wciąż O(n).

Przynajmniej ja tak to sobie tłumacze