Aufgabe:
Sei \( \alpha \in \mathbb{N}_{\geq 0} \) eine Konstante. Zeigen Sie, dass man ein Feld der Länge \( n \) mit Zahlen aus dem Wertebereich \( \left\{0, \ldots, n^{\alpha}\right\} \) mittels Radixsort in Zeit \( \mathcal{O}(n) \) sortieren kann.
Gehen Sie wie folgt vor:
1. Überlegen Sie sich, welche die kleinste und welche die größte \( b \)-adische Zahl ist, die Sie mit einer Basis \( b \in \mathbb{N}_{>0} \) und einer Ziffernanzahl \( d \in \mathbb{N}_{>0} \) erhalten können, indem Sie per Induktion zeigen, dass \( \sum \limits_{i=0}^{d-1} b^{i}=\frac{b^{d}-1}{b-1} \) gilt.
Kann mir jemand bitte helfen? :)