Aufgabe:
Sei α∈N≥0 eine Konstante. Zeigen Sie, dass man ein Feld der Länge n mit Zahlen aus dem Wertebereich {0,…,nα} mittels Radixsort in Zeit 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∈N>0 und einer Ziffernanzahl d∈N>0 erhalten können, indem Sie per Induktion zeigen, dass i=0∑d−1bi=b−1bd−1 gilt.
Kann mir jemand bitte helfen? :)