Master teorema se koristi za asimptotsku ocenu slozenosti (rekurzivnog) algoritma kod koga se problem velicine (dimenzije) n resava tako sto se deli na a potproblema (a >= 1) velicine (n / b) (gde je b > 1, strogo vece od jedinice), koji se nakon toga rese na isti nacin i kada se resi tih a potproblema, onda se resenja tih potproblema “iskombinuju” da bi se dobilo resenje polaznog problema.
Tada se slozenost zapisuje u obliku formule
O(1), ako je n = 1
T(n) =
a * T(n / b) + f(n), ako je n > 1
Ovde je f(n) funkcija koja predstavlja slozenost kombinovanja resenja potproblema i/ili deobe probleme na potproblema
Tada slozenost T(n) zavisi od broja log_b a (tj. logaritam od a za osnovu b)
Preciznije, racuna se n na log_b a (n ^ (log_b a)) i poredi sa f(n)
Mogu nastupiti tri slicaja
1. Ako je f(n) = O(n ^ (log_b (a) – epsilon)), za neko epsilon > 0, onda je
T(n) = Theta(n ^ (log_b a))
2. Ako je f(n) = Theta(n ^ (log_b a)), onda je
T(n) = Theta(n ^ (log_b a) * log n)
3. Ako je f(n) = Omega(n ^ (log_b a + epsilon)), za neko epsilon > 0,
i ako postoji konstanta c < 1, tako da za n > no vazi a * f(n / b) <= c * f(n), onda je T(n) = Theta(f(n))
Uslov da postoji konstanta c < 1, tako da za n > no vazi a * f(n / b) <= c * f(n) se zove USLOV REGULARNOSTI.
Pisemo da je f(n) = O(g(n)) ako postoji konstanta c > 0 i prirodan broj n0 tako da za svako n > n0 vazi da je f(n) <= c * g(n).
Na primer, ako je f(n) = 2*n^2 + 3 * n, onda je
f(n) = 2 * n^2 + 3 * n <= 3 * n^2 + 3 * n^2 = 5 * n^2, pa je f(n) = O(n^2)
Pisemo da je f(n) = Theta(g(n)), ako postoje konstante c2 > c1 > 0 i prirodan broj n0, tako da za svako n > n0 vazi
c1 * g(n) <= f(n) <= c2 * g(n).
Pisemo da je f(n) = Omega(g(n)) ako postoji konstanta c > 0 i prirodan broj n0 tako da za svako n > n0 vazi da je f(n) >= c * g(n).
T(n) = 4 T(n / 2) + 3n
a = 4, b = 2, f(n) = 3n
log_b(a) = log_2(4) = 2
n^(log_b(a)) = n^2
f(n) = 3*n = O(n^(2-0.5))
Znaci T(n) = Teta(n^2)
T(n) = 8 T(n/2) + n^4
a = 8, b = 2, f(n) = n^4
log_b(a) = log_2 (8) = 3
n ^ (log_b(a)) n^3
f(n) = n^4 = Omega(n^(3_0,75))
REGULARNOST:
Treba da proverimo da li postoji broj c < 1 takav da je
a * f(n / b) <= c * f(n)
a * f(n / b)= 8*f(n / 2)= 8*(n / 2)^4=8*n^4/2^4=8*n^4/16=(1 / 2)*n^4
tj.
a * f(n / b) <= (1 / 2) * f(n)
Zbog toga je
T(n) = Teta(f(n)) = Teta(n^4)
NTP 