Master-Theorem

Rekursionsgleichungen haben oft die Form

Das Master-Theorem gibt an, wie man solche Gleichungen lösen kann:

1. Falls für ein , dann:
2. Falls , dann:
3. Falls für ein und falls für ein und alle , dann: