Analyse der Größe der erzeugten Ausgabe:
Sei die Anzahl der generierten Verlegebefehle bei Aufruf von
Offenbar: | = | 1 | |||
= | = | ||||
d.h., die Wertetabelle beginnt wie folgt:
Verdacht:
Beweis durch Induktion
Induktionsverankerung:
Induktionsschritt: Sei bis bewiesen:
= | = = = | |
Rekursionsgleichung | Induktionsannahme |