Μάστερ Θεώρημα

Το μάστερ θεώρημα (master theorem) είναι ειδική περίπτωση του θεωρήματος Akra-Bazzi. Χρησιμοποιείται στην ανάλυση αλγορίθμων για τον προσδιορισμό του ασυμπτωτικού ορίου μιας αναδρομικής συνάρτησης. Ωστόσο δεν επιλύεται κάθε αναδρομική σχέση με το μάστερ θεώρημα.

Γενική Μορφή 

Η γενική μορφή του θεωρήματος είναι:

,όπου  είναι η αναδρομική σχέση,  και  είναι σταθερές και  είναι μια μη αρνητική συνάρτηση ανεξάρτητη της .

Για να εφαρμοστεί το μάστερ θεώρημα θα πρέπει να ισχύουν για τις δυο σταθερές  οι εξής ανισότητες:
 και .

Το μάστερ θεώρημα χωρίζεται σε τρεις περιπτώσεις, οι οποίες μπορούν συνήθως να δώσουν λύση. Παρόλα αυτά υπάρχει και μια ειδική περίπτωση, η οποία μπορεί να χρησιμοποιηθεί όταν δεν ταιριάζουν όλες οι άλλες.

Περίπτωση πρώτη 

Αν  , τότε

Περίπτωση δεύτερη 

Αν , τότε

Περίπτωση τρίτη 

Αν  και , τότε

Συμπέρασμα 

Δηλαδή, ο ασυμπτωτικά μεγαλύτερος απο τους όρους  και  καθορίζει την λύση της εξίσωσης.

 
Μαθηματική ανάλυση Αλγόριθμοι