Master Theorem är ett verktyg som används för att lösa återkommande relationer som uppstår i analysen av dela-och-härska-algoritmer. Master Theorem ger ett systematiskt sätt att lösa återkommande relationer av formen:

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

1. där a, b och f(n) är positiva funktioner och n är storleken på problemet. Mastersatsen ger förutsättningar för att lösningen av recidiven ska vara i form av O(n^k) för någon konstant k, och den ger en formel för att bestämma värdet av k.
2. Den avancerade versionen av Master Theorem ger en mer generell form av satsen som kan hantera återkommande relationer som är mer komplexa än grundformen. Den avancerade versionen av Master Theorem kan hantera upprepningar med flera termer och mer komplexa funktioner.
3. Det är viktigt att notera att Master Theorem inte är tillämplig på alla återkommande relationer, och det kanske inte alltid ger en exakt lösning på ett givet återfall. Det är dock ett användbart verktyg för att analysera tidskomplexiteten hos dela-och-härska-algoritmer och ger en bra utgångspunkt för att lösa mer komplexa upprepningar.

Master Theorem används för att bestämma körtiden för algoritmer (divide and conquer-algoritmer) i termer av asymptotiska notationer.
Tänk på ett problem som löses med hjälp av rekursion.

 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>

Ovanstående algoritm delar in problemet i a delproblem, vart och ett av storlek n/b och lösa dem rekursivt för att beräkna problemet och det extra arbetet som görs för problemet ges av f(n), dvs tiden för att skapa delproblemen och kombinera deras resultat i ovanstående procedur.

Så enligt mastersatsen kan körtiden för ovanstående algoritm uttryckas som:

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

där n = storleken på problemet
a = antal delproblem i rekursionen och a>= 1
n/b = storleken på varje delproblem
f(n) = kostnaden för arbete som utförs utanför de rekursiva anropen som att dela upp i delproblem och kostnaden för att kombinera dem för att få lösningen.

Inte alla återkommande relationer kan lösas med hjälp av mastersatsen, dvs om

• T(n) är inte monoton, ex: T(n) = sin n
• f(n) är inte ett polynom, ex: T(n) = 2T(n/2) + 2ⁿ

Detta teorem är en förhandsversion av mastersatsen som kan användas för att bestämma körtiden för dela och erövra algoritmer om upprepningen är av följande form:-

där n = storleken på problemet
a = antal delproblem i rekursionen och a>= 1
n/b = storleken på varje delproblem
b> 1, k>= 0 och p är ett reellt tal.

Sedan,

1. om a> b^k, då T(n) = θ(n^logga_ba)
2. om a = b^k, då
   (a) om p> -1, så är T(n) = θ(n^logga_balogga^p+1n)
   (b) om p = -1, så är T(n) = θ(n^logga_baloglogn)
   (c) om p <-1, så är T(n) = θ(n^logga_ba)
   
3. Om en okej då
   (a) om p>= 0, då är T(n) = θ(n^klogga^sidn)
   (b) om p <0, så är T(n) = θ(n^k)
   

Tidskomplexitetsanalys –

Exempel-1: Binär sökning – T(n) = T(n/2) + O(1)
a = 1, b = 2, k = 0 och p = 0
b^k= 1. Så, a = b^koch p> -1 [Fall 2.(a)]
T(n) = θ(n^logga_balogga^p+1n)
T(n) = θ(logn) Exempel-2: Slå samman sortering – T(n) = 2T(n/2) + O(n)
a = 2, b = 2, k = 1, p = 0
b^k= 2. Så, a = b^koch p> -1 [Fall 2.(a)]
T(n) = θ(n^logga_balogga^p+1n)
T(n) = θ(nlogn) Exempel-3: T(n) = 3T(n/2) + n²
a = 3, b = 2, k = 2, p = 0
b^k= 4. Så, en k och p = 0 [Fall 3.(a)]
T(n) = θ(n^klogga^sidn)
T(n) = θ(n²)

Exempel-4: T(n) = 3T(n/2) + log²n
a = 3, b = 2, k = 0, p = 2
b^k= 1. Så, a> b^k[Fall 1]
T(n) = θ(n^logga_ba)
T(n) = θ(n^logga₂3)

Exempel-5: T(n) = 2T(n/2) + nlog²n
a = 2, b = 2, k = 1, p = 2
b^k= 2. Så, a = b^k[Fall 2.(a)]
T(n) = θ(n^logga_balogga^p+1n )
T(n) = θ(n^logga₂2logga³n)
T(n) = θ(nlog³n)

Exempel-6: T(n) = 2ⁿT(n/2) + nⁿ
Denna upprepning kan inte lösas med ovanstående metod eftersom funktionen inte har formen T(n) = aT(n/b) + θ(n^klogga^sidn)

GATE Övningsfrågor –

• GATE-CS-2017 (uppsättning 2) | Fråga 56
• GATE IT 2008 | Fråga 42
• GATE CS 2009 | Fråga 35

Här är några viktiga punkter att tänka på när det gäller Master Theorem:

1. Dela-och-härska upprepningar: Mastersatsen är specifikt utformad för att lösa upprepningsrelationer som uppstår i analysen av dela-och-härska-algoritmer.
2. Upprepningens form: Mastersatsen gäller upprepningsrelationer av formen T(n) = aT(n/b) + f(n), där a, b och f(n) är positiva funktioner och n är storleken av problemet.
3. Tidskomplexitet: Mastersatsen ger förutsättningar för att lösningen av recidivet ska vara i form av O(n^k) för någon konstant k, och den ger en formel för att bestämma värdet av k.
4. Avancerad version: Den avancerade versionen av Master Theorem ger en mer generell form av satsen som kan hantera återkommande relationer som är mer komplexa än grundformen.
5. Begränsningar: Master Theorem är inte tillämplig på alla återkommande relationer, och det kanske inte alltid ger en exakt lösning på ett givet återfall.
6. Användbart verktyg: Trots sina begränsningar är Master Theorem ett användbart verktyg för att analysera tidskomplexiteten hos divide-and-ereg-algoritmer och ger en bra utgångspunkt för att lösa mer komplexa upprepningar.
7. Kompletteras med andra tekniker: I vissa fall kan Mastersatsen behöva kompletteras med andra tekniker, såsom substitutionsmetoden eller iterationsmetoden, för att helt lösa en given återfallsrelation.