Akú zložitosť má toto triedenie? Na začiatku prejdeme celé pole dĺžky $n$, a pre každý index urobíme konštantne veľa operácií - zväčšíme hodnotu na nejakom indexe poľa. Táto časť má teda zložitosť $O(n)$
Následne toto celé pole prejdeme, a pre každý index vypíšeme toľko čísel, aká je na tom indexe hodnota. Ak vieme, že čísla sú z rozsahu $\langle 0, k \rangle$, tak prejsť toto pole nám trvá $O(k)$ času. Okrem toho tieto hodnoty ešte vypisujeme, ale keďže dokopy vypisujeme $n$ čísel, tak nám to trvá najviac $O(n)$ času.
Ak teda triedime $n$ čísel z rozsahu $\langle 0, k \rangle$, tak to vieme urobiť v časovej zložitosti $O(n+k)$.