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

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

Γενική Μορφή

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

$T(n)=a\cdot T{\bigg (}{\frac {n}{b}}{\bigg )}+f(n)$

,όπου $T(n)$ είναι η αναδρομική σχέση, $a$ και $b$ είναι σταθερές και $f(n)$ είναι μια μη αρνητική συνάρτηση ανεξάρτητη της $T(n)$.

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

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

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

Αν $f(n)=O(n^{{log}_{b}a})$, τότε $T(n)=\Theta (n^{{log}_{b}a}).$

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

Αν $f(n)=\Theta (n^{{log}_{b}a})$, τότε $T(n)=\Theta (n^{{log}_{b}a}\cdot logn).$

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

Αν $f(n)=\Omega (n^{{log}_{b}a})$ και $af(n/b)<cf(n),c={\text{σταθ.}}$, τότε $T(n)=\Theta (f(n)).$

Συμπέρασμα

Δηλαδή, ο ασυμπτωτικά μεγαλύτερος απο τους όρους $f(n)$ και $n^{{log}_{b}a}$ καθορίζει την λύση της εξίσωσης.