Radix est-il vraiment O (n) pour trier les entiers 32 bits?

Question

J'essayais d'analyser le tri de Radix en termes de temps et d'espace. Supposons que nous recevons des entiers N 32 bits $ N que nous voudrions trier en examinant d'abord les chiffres les moins importants.

$ k $ est le montant total des bits avec lesquels vous travaillerez à chaque étape. Donc, au début, vous regardez les premiers bits $ k $ et triez les éléments avec le tri de comptage. Ensuite, vous regardez les bits $ K $ suivants, etc.

Au total, nous devions exécuter le comptage de tri $ frac {32} {k} $ fois. Dans la phase de tri de comptage, nous devrons tous les deux scanner le tableau d'entrée et également le tableau de godet, où le tableau d'entrée est de taille $ n $ et le tableau de godet est de taille 2 ^ k $. En d'autres termes, le temps d'exécution sera $ theta ( frac {32} {k} (n + 2 ^ k)) $. Quant à l'espace, nous aurons besoin d'un tableau temporaire supplémentaire de taille $ n $ pendant la phase de tri de comptage, ainsi que d'un tableau pour le seau, donc dans le total, l'espace sera $ theta (2n + 2 ^ k) $ $

Donc nous avons:

Temps: $ theta ( frac {32} {k} (n + 2 ^ k)) $

Espace: $ theta (2n + 2 ^ k) $

Suis-je le seul à ne pas voir pourquoi c'est $ o (n) $?