Το Θεώρημα Κυριαρχίας αποτελεί έναν εύκολο τρόπο υπολογισμού αναδρομικών εξισώσεων της μορφής T(n)= aT(n/b)+f(n) όπου για τις  σταθερές ισχύει   a≥1 και b>1 και η f(n) είναι μια θετική συνάρτηση.
Συνεπώς για τέτοιου είδους εξισώσεις θεωρούμε ότι ο χρόνος αναδρομής είναι   και ο χρόνος σύνθεσης λύσεων είναι f(n).

Αναλυτικά για το Θεώρημα Κυριαρχίας θα έχουμε :

1) Η f(n) είναι

για κάποιο ε>0 τότε η T(n) είναι

Η f(n) είναι πολυωνυμικά μικρότερη από το



2) Η f(n) είναι
Η f(n) είναι πολυωνυμικά ίδιας τάξης μεγέθους με 

3) Η f(n) είναι





για κάποιο ε>0 και ισχύει :
τότε η T(n) είναι Θ(f(n)) για κάποιο c <1 . Δηλαδή η f(n) πολυωνυμικά μεγαλύτερη από .
Βασικά εργαζόμαστε ως εξής :
Υψώνουμε την βάση του λογαρίθμου b μέχρι το όρισμά του a. στην συνέχεια εξετάζουμε και συγκρίνουμε τους εκθέτες οπότε μπορούμε να συμπεράνουμε τα απαραίτητα για την τιμή του c .
Θα δούμε ένα παράδειγμα.
Έστω να υπολογιστή η αναδρομική εξίσωση T(n)= 4T(n/3)+ n^2
θα είναι
f(n)=n^2,  a=4 ,b=3
τότε 3^0=1, 3^1=3, 3^2=9  >a    άρα = n^c   με c<2

συνεπώς η f(n) είναι πολυωνυμικά μεγαλύτερης τάξης της 

Ακόμα = 4f(n/3) < cn^2 <=> 4(n/3)^2 = c n^2 <=> c> 4/9 δηλαδή
πρέπει  4/9 < c <1, ισχύει για c= 1/2 <1 οπότε ,
από (3) περίπτωση του Θεωρήματος Κυριαρχίας η T(n) = Θ(f(n))= Θ(n^2)

Εξαιρέσεις 

• Μια ιδιαίτερη μορφή υλοποίησης του Θεωρήματος της Κυριαρχίας είναι και η επόμενη άσκηση.

Έστω η αναδρομική εξίσωση Τ(n) =T(n/3)+T(n/4)+ nlogn
Η T(n) γράφεται 
Τ1(n)= T(n/3)+T(n/3)+nlogn= 2T(n/3)+nlogn μικρότερος χρόνος 

T2(n)= T(n/4)+T(n/4)+nlogn =2T(n/4)+nlogn μεγαλύτερος χρόνος 

Ισχύει ότι  Τ1(n)≤ T(n)≤  T2(n) (a)

Για την T1 είναι f(n)= nlogn , και n^loga =n^c , με c<1 δηλαδή η f(n) πολυωνυμικά μεγαλύτερη.

Ακόμα af(n/b)< cf(n) <=> 2f(n/4) < cnlogn <=> 2 n/4*logn/4 < c n logn<=> 
1/2(logn-log4) <c logn ισχύει,  αν θέσω c=2/3 >1/2

Άρα από (3) περίπτωση Θεωρήματος Κυριαρχίας έχω ότι T1(n)= Θ(nlogn)
Ομοίως δουλεύουμε και για την T2 όπου καταλήγουμε  Τ2(n)= Θ(nlogn)= T1(n) 

Οπότε από την (α) συμπεραίνουμε ότι T(n) =Θ(nlogn)