Vollständige Induktion bei Radixsort

Question

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? :)

Answer 1

Zeig doch mal den Induktionsanfang für d=1, wie würdest du das machen?

Anschließend musst du zeigen wenn

$$\sum \limits_{i=0}^{d-1} b^{i}=\frac{b^{d}-1}{b-1}$$

dann gilt auch

$$\sum \limits_{i=0}^{(d+1)-1} b^{i}=\frac{b^{d+1}-1}{b-1}$$

Versuche mal von der zweiten Summe so Summanden abzuspalten, dass du die erste Gleichung einsetzen kannst.

Comments

Vielen Dank, das hilft mir. Jedoch verstehe ich eine Sache immer wenn mir etwas komplett vor Augen geführt wird und ich das so Schritt für Schritt durchgehe. Könntest du mir den Beweis komplett aufschreiben und ich sage dir dann was noch unklar ist (falls etwas unklar ist)? Das wäre sehr lieb.

:)