Master Theorem er et verktøy som brukes til å løse gjentakelsesrelasjoner som oppstår i analysen av del-og-hersk-algoritmer. Master Theorem gir en systematisk måte å løse gjentakende relasjoner av formen:

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

1. hvor a, b og f(n) er positive funksjoner og n er størrelsen på problemet. Hovedteoremet gir betingelser for at løsningen av gjentakelsen skal være i form av O(n^k) for en konstant k, og den gir en formel for å bestemme verdien av k.
2. Den avanserte versjonen av Master Theorem gir en mer generell form av teoremet som kan håndtere tilbakefallsrelasjoner som er mer komplekse enn grunnformen. Den avanserte versjonen av Master Theorem kan håndtere gjentakelser med flere termer og mer komplekse funksjoner.
3. Det er viktig å merke seg at Master Theorem ikke er anvendelig for alle gjentakelsesrelasjoner, og det kan ikke alltid gi en eksakt løsning på en gitt gjentakelse. Det er imidlertid et nyttig verktøy for å analysere tidskompleksiteten til dele-og-hersk-algoritmer og gir et godt utgangspunkt for å løse mer komplekse gjentakelser.

Master Theorem brukes til å bestemme kjøretiden for algoritmer (divide and conquer-algoritmer) i form av asymptotiske notasjoner.
Vurder et problem som er løst ved hjelp av rekursjon.

 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>

Algoritmen ovenfor deler problemet inn i en delproblemer, hver av størrelse n/b og løse dem rekursivt for å beregne problemet, og det ekstra arbeidet som gjøres for problemet er gitt av f(n), det vil si tiden for å lage delproblemene og kombinere resultatene i prosedyren ovenfor.

Så i henhold til masterteoremet kan kjøretiden til algoritmen ovenfor uttrykkes som:

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

hvor n = størrelsen på problemet
a = antall delproblemer i rekursjonen og a>= 1
n/b = størrelsen på hvert delproblem
f(n) = kostnaden for arbeid utført utenfor de rekursive samtalene som å dele inn i delproblemer og kostnadene ved å kombinere dem for å få løsningen.

Ikke alle tilbakefallsrelasjoner kan løses ved bruk av masterteoremet, dvs. hvis

• T(n) er ikke monoton, eks: T(n) = sin n
• f(n) er ikke et polynom, eks: T(n) = 2T(n/2) + 2ⁿ

Dette teoremet er en forhåndsversjon av masterteoremet som kan brukes til å bestemme kjøretiden for dele- og erobringsalgoritmer hvis gjentakelsen er av følgende form:

hvor n = størrelsen på problemet
a = antall delproblemer i rekursjonen og a>= 1
n/b = størrelsen på hvert delproblem
b> 1, k>= 0 og p er et reelt tall.

Deretter,

1. hvis a> b^k, så T(n) = θ(n^Logg_ben)
2. hvis a = b^k, deretter
   (a) hvis p> -1, så er T(n) = θ(n^Logg_benLogg^p+1n)
   (b) hvis p = -1, så er T(n) = θ(n^Logg_benpålogging)
   (c) hvis p <-1, så er T(n) = θ(n^Logg_ben)
   
3. hvis en k, da
   (a) hvis p>= 0, så er T(n) = θ(n^kLogg^sn)
   (b) hvis p <0, så er T(n) = θ(n^k)
   

Tidskompleksitetsanalyse –

Eksempel-1: Binært søk – T(n) = T(n/2) + O(1)
a = 1, b = 2, k = 0 og p = 0
b^k= 1. Så, a = b^kog p> -1 [tilfelle 2.(a)]
T(n) = θ(n^Logg_benLogg^p+1n)
T(n) = θ(logn) Eksempel-2: Sammenslåingssortering – T(n) = 2T(n/2) + O(n)
a = 2, b = 2, k = 1, p = 0
b^k= 2. Så, a = b^kog p> -1 [tilfelle 2.(a)]
T(n) = θ(n^Logg_benLogg^p+1n)
T(n) = θ(nlogn) Eksempel-3: T(n) = 3T(n/2) + n²
a = 3, b = 2, k = 2, p = 0
b^k= 4. Så, en k og p = 0 [tilfelle 3.(a)]
T(n) = θ(n^kLogg^sn)
T(n) = θ(n²)

Eksempel-4: T(n) = 3T(n/2) + log²n
a = 3, b = 2, k = 0, p = 2
b^k= 1. Så, a> b^k[Case 1]
T(n) = θ(n^Logg_ben)
T(n) = θ(n^Logg₂3)

Eksempel-5: T(n) = 2T(n/2) + nlog²n
a = 2, b = 2, k = 1, p = 2
b^k= 2. Så, a = b^k[Tilfelle 2.(a)]
T(n) = θ(n^Logg_benLogg^p+1n )
T(n) = θ(n^Logg₂2Logg³n)
T(n) = θ(nlog³n)

Eksempel-6: T(n) = 2ⁿT(n/2) + nⁿ
Denne gjentakelsen kan ikke løses ved å bruke metoden ovenfor siden funksjonen ikke har formen T(n) = aT(n/b) + θ(n^kLogg^sn)

GATE øvingsspørsmål –

• GATE-CS-2017 (sett 2) | Spørsmål 56
• GATE IT 2008 | Spørsmål 42
• GATE CS 2009 | Spørsmål 35

Her er noen viktige punkter å huske på angående Master Theorem:

1. Del-og-hersk-gjentakelser: Master-teoremet er spesielt utviklet for å løse gjentakelsesrelasjoner som oppstår i analysen av dele-og-hersk-algoritmer.
2. Gjentakelsens form: Masterteoremet gjelder gjentaksrelasjoner av formen T(n) = aT(n/b) + f(n), der a, b og f(n) er positive funksjoner og n er størrelsen av problemet.
3. Tidskompleksitet: Hovedteoremet gir betingelser for at løsningen av gjentakelsen skal være i form av O(n^k) for en eller annen konstant k, og den gir en formel for å bestemme verdien av k.
4. Avansert versjon: Den avanserte versjonen av Master Theorem gir en mer generell form av teoremet som kan håndtere gjentaksrelasjoner som er mer komplekse enn grunnformen.
5. Begrensninger: Masterteoremet er ikke aktuelt for alle gjentakelsesrelasjoner, og det er ikke alltid den gir en eksakt løsning på en gitt gjentakelse.
6. Nyttig verktøy: Til tross for sine begrensninger er Master Theorem et nyttig verktøy for å analysere tidskompleksiteten til dele-og-hersk-algoritmer og gir et godt utgangspunkt for å løse mer komplekse gjentakelser.
7. Supplert med andre teknikker: I noen tilfeller kan Masterteoremet måtte suppleres med andre teknikker, for eksempel substitusjonsmetoden eller iterasjonsmetoden, for å fullstendig løse en gitt gjentakelsesrelasjon.