Radix è davvero O (N) per l'ordinamento di numeri interi a 32 bit?

Question

Stavo cercando di analizzare Radix Ord in termini di tempo e spazio. Supponiamo che ci vengano dati numeri interi da $ n $ 32 bit che vorremmo ordinare guardando prima le cifre almeno significative.

$ k $ è l'importo totale dei bit con cui lavorerai ad ogni passaggio. Quindi all'inizio guardi i primi $ k $ bit e ordina gli elementi con il conteggio. Quindi guardi i prossimi $ k $ bit ecc.

In totale dovremmo eseguire il conteggio di ordinamento $ frac {32} {k} $ volte. Nella fase di ordinamento del conteggio dovremo entrambi scansionare l'array di input e anche l'array di benna, in cui l'array di input è di dimensioni $ n $ e l'array di bucket è di taglia $ 2^k $. In altre parole, il tempo di esecuzione sarà $ theta ( frac {32} {k} (n+2^k)) $. Per quanto riguarda lo spazio, avremo bisogno di una gamma extra temporanea di dimensioni $ n $ durante la fase di ordinamento del conteggio e anche un array per il secchio, quindi in totale lo spazio sarà $ theta (2n + 2^k) $

Quindi abbiamo:

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

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

Sono l'unico che non riesce a capire perché questo è $ o (n) $?