Glavni izrek je orodje, ki se uporablja za reševanje ponavljajočih se relacij, ki se pojavijo pri analizi algoritmov deli in vladaj. Glavni izrek zagotavlja sistematičen način reševanja rekurenčnih relacij oblike:

T(n) = aT(n/b) + f(n)

1. kjer so a, b in f(n) pozitivne funkcije in je n velikost problema. Glavni izrek zagotavlja pogoje, da je rešitev ponovitve v obliki O(n^k) za neko konstanto k, in daje formulo za določanje vrednosti k.
2. Napredna različica glavnega izreka zagotavlja bolj splošno obliko izreka, ki lahko obravnava ponavljajoče se relacije, ki so bolj zapletene od osnovne oblike. Napredna različica Master Theorem lahko obravnava ponovitve z več členi in bolj zapletenimi funkcijami.
3. Pomembno je omeniti, da glavni izrek ni uporaben za vse povratne relacije in morda ne zagotavlja vedno natančne rešitve dane ponovitve. Je pa uporabno orodje za analizo časovne kompleksnosti algoritmov deli in vladaj in zagotavlja dobro izhodišče za reševanje bolj zapletenih ponovitev.

Glavni izrek se uporablja za določanje časa delovanja algoritmov (algoritmov deli in vladaj) v smislu asimptotičnih zapisov.
Razmislite o problemu, ki je rešen z rekurzijo.

 function f (input x size n) if (n else divide x into a subproblems of size n/b call f recursively to solve each subproblem Combine the results of all sub-problems>

Zgornji algoritem razdeli problem na a podproblemov, od katerih je vsak velikosti n/b, in jih rekurzivno rešiti za izračun težave, dodatno delo, opravljeno za težavo, pa poda f(n), tj. čas za ustvarjanje podproblemov in združevanje njihovih rezultatov v zgornjem postopku.

Tako lahko v skladu z glavnim izrekom čas izvajanja zgornjega algoritma izrazimo kot:

 T(n) = aT(n/b) + f(n)>

kjer je n = velikost problema
a = število podproblemov v rekurziji in a>= 1
n/b = velikost vsakega podproblema
f(n) = stroški dela, opravljenega zunaj rekurzivnih klicev, kot je razdelitev na podprobleme, in stroški njihovega združevanja, da bi dobili rešitev.

Vseh rekurenčnih relacij ni mogoče rešiti z uporabo glavnega izreka, tj. če

• T(n) ni monoton, npr.: T(n) = sin n
• f(n) ni polinom, npr.: T(n) = 2T(n/2) + 2ⁿ

Ta izrek je napredna različica glavnega izreka, ki se lahko uporabi za določitev časa delovanja algoritmov deli in vladaj, če je ponovitev naslednje oblike:

kjer je n = velikost problema
a = število podproblemov v rekurziji in a>= 1
n/b = velikost vsakega podproblema
b> 1, k>= 0 in p je realno število.

potem,

1. če a> b^k, potem je T(n) = θ(n^dnevnik_ba)
2. če je a = b^k, potem
   (a) če je p> -1, potem je T(n) = θ(n^dnevnik_badnevnik^p+1n)
   (b) če je p = -1, potem je T(n) = θ(n^dnevnik_baprijava)
   (c) če je p <-1, potem je T(n) = θ(n^dnevnik_ba)
   
3. če k, potem
   (a) če je p>= 0, potem je T(n) = θ(n^kdnevnik^strn)
   (b) če je p <0, potem je T(n) = θ(n^k)
   

Analiza časovne kompleksnosti –

Primer-1: Binarno iskanje – T(n) = T(n/2) + O(1)
a = 1, b = 2, k = 0 in p = 0
b^k= 1. Torej je a = b^kin p> -1 [Primer 2.(a)]
T(n) = θ(n^dnevnik_badnevnik^p+1n)
T(n) = θ(logn) Primer-2: Razvrščanje z združitvijo – T(n) = 2T(n/2) + O(n)
a = 2, b = 2, k = 1, p = 0
b^k= 2. Torej je a = b^kin p> -1 [Primer 2.(a)]
T(n) = θ(n^dnevnik_badnevnik^p+1n)
T(n) = θ(nlogn) Primer-3: T(n) = 3T(n/2) + n²
a = 3, b = 2, k = 2, p = 0
b^k= 4. Torej, a k in p = 0 [Primer 3.(a)]
T(n) = θ(n^kdnevnik^strn)
T(n) = θ(n²)

Primer-4: T(n) = 3T(n/2) + log²n
a = 3, b = 2, k = 0, p = 2
b^k= 1. Torej, a> b^k[1. primer]
T(n) = θ(n^dnevnik_ba)
T(n) = θ(n^dnevnik₂3)

Primer-5: T(n) = 2T(n/2) + nlog²n
a = 2, b = 2, k = 1, p = 2
b^k= 2. Torej je a = b^k[Primer 2.(a)]
T(n) = θ(n^dnevnik_badnevnik^p+1n )
T(n) = θ(n^dnevnik₂2dnevnik³n)
T(n) = θ(nlog³n)

Primer-6: T(n) = 2ⁿT(n/2) + nⁿ
Te ponovitve ni mogoče rešiti z zgornjo metodo, ker funkcija ni oblike T(n) = aT(n/b) + θ(n^kdnevnik^strn)

GATE vprašanja za vadbo –

• GATE-CS-2017 (Sklop 2) | 56. vprašanje
• GATE IT 2008 | 42. vprašanje
• GATE CS 2009 | 35. vprašanje

Tukaj je nekaj pomembnih točk, ki jih morate upoštevati v zvezi z glavnim izrekom:

1. Ponovitve razdeli in vladaj: Glavni izrek je posebej zasnovan za reševanje relacij ponovitev, ki se pojavijo pri analizi algoritmov deli in vladaj.
2. Oblika ponovitve: Glavni izrek velja za povratne relacije oblike T(n) = aT(n/b) + f(n), kjer so a, b in f(n) pozitivne funkcije in je n velikost problema.
3. Časovna kompleksnost: Glavni izrek zagotavlja pogoje, da je rešitev ponovitve v obliki O(n^k) za neko konstanto k, in daje formulo za določanje vrednosti k.
4. Napredna različica: Napredna različica glavnega izreka zagotavlja splošnejšo obliko izreka, ki lahko obravnava ponovitvene relacije, ki so bolj zapletene od osnovne oblike.
5. Omejitve: Glavni izrek ni uporaben za vse ponovitvene relacije in morda ne zagotavlja vedno natančne rešitve dane ponovitve.
6. Uporabno orodje: Glavni izrek je kljub svojim omejitvam uporabno orodje za analizo časovne kompleksnosti algoritmov deli in vladaj in zagotavlja dobro izhodišče za reševanje bolj zapletenih ponovitev.
7. Dopolnjeno z drugimi tehnikami: V nekaterih primerih bo glavni izrek morda treba dopolniti z drugimi tehnikami, kot sta metoda zamenjave ali metoda ponovitve, da bi v celoti rešili dano relacijo ponavljanja.