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 |