Επίλυση Αναδρομικών Εξισώσεων T(n) με τη μέθοδο της επανάληψης.
Για την επίλυση αναδρομικών εξισώσεων χρησιμοποιούμε δύο βασικούς τρόπους.
Ο πρώτος είναι με την μέθοδο επανάληψης με την βοήθεια του αλγεβρικού υπολογισμού, ή με τα δέντρα αναδρομής και ο δεύτερος με την μέθοδο της αντικατάστασης.
Βασική ιδέα επίλυσης με την μέθοδο επανάληψης , είναι η επανάληψη. Με τον τρόπο αυτό, προσπαθούμε να εκφράσουμε την αναδρομική εξίσωση σαν άθροισμα και να βρούμε έναν "κλειστό τύπο" όπου στην συνέχεια θα τον υπολογίσουμε.
Κατά την αλγεβρική επίλυση θα πρέπει να είμαστε προσεκτικοί με τις πράξεις αφού συχνά οδηγεί σε πολύπλοκους αλγεβρικούς τύπους και ακόμα θα πρέπει να προσέξουμε τον υπολογισμό της "αρχικής συνθήκης" ή του"κλειστού τύπου", αφού από αυτόν εξαρτάται η ορθότητα του αποτελέσματος.
Ας δούμε λοιπόν ένα παράδειγμα υπολογισμού αναδρομικής εξίσωσης με την βοήθεια της αλγεβρικής επίλυσης καθώς και τα βήματα της επανάληψης.
Έστω ότι δίνεται η εξίσωση:
θα είναι :
θα πρέπει να σκεφτούμε ότι η αναδρομή τελειώνει όταν
(στο παραπάνω καταλήγουμε από γνωστό τύπο λογαρίθμων)
Συνεπώς, υπολογίζουμε τον κλειστό τύπο κάνοντας τις αντικαταστάσεις
Ένα ακόμα παράδειγμα υπολογισμού αναδρομικής εξίσωσης, αυτή την φορά με την βοήθεια του δέντρου αναδρομής.
Έστω η αναδρομική εξίσωση:
Ξεκινώ από το n θα είναι
| Επίπεδο | Άθροισμα | |
| n | 0 | n |
| n/2 + n/2 | 1 | n |
| n/4 + n/4 + n/4 +n/4 | 2 | n |
| ................... | i | n |
| T(n) |
Άρα θα είναι T(n)=n + n +.....+ n + n= n logn = Θ(nlogn)
αφού το ύψος του δέντρου είναι logn και επαναλαμβάνεται n φορές.
Θα έχουμε την ευκαιρία να αναφερθούμε και περαιτέρω στην επίλυση αναδρομικών εξισώσεων και ιδιαίτερα με την χρήση του Θεωρήματος Κυριαρχίας .