Teorema 1 (Metode Master) Diberikan suatu rekurensi T (n) = aT (n/b) + f (n) , jika n ≥ n0, untuk suatu n0 elemen N dan T (n) konstan untuk 0 ≤ n < n0. Apabila a ≥ 1, b > 1 keduanya adalah nilai yang konstan dan f (n) adalah fungsi yang asimtotik positif, maka:
Gunakan Teorema 1 untuk mencari solusi dari setiap rekurensi berikut dalam notasi . Jika metode master tidak dapat diterapkan, gunakan metode lain yang Anda ketahui. Asumsikan bahwa T (n) konstan untuk n yang cukup kecil.
(a). T (n) = 3T (n/2) + n.
Solusi T (n) = 3T (n/2) + n menggunakan master theorem kasus 1.
(b). T (n) = 2T (n/2) + n^3.
Solusi T (n) = 2T (n/2) + n^3 menggunakan master theorem kasus 3.
(c). T (n) = 7T (n/3) + n^2.
Solusi T (n) = 7T (n/3) + n^2 menggunakan master theorem kasus 3.
(d). T (n) = 2T (n/2) + n lg n.
Solusi T (n) = 2T (n/2) + n lg n menggunakan master theorem kasus 2.
(e). T (n) = 4T (n/2) + n^2 √n.
Solusi T (n) = 4T (n/2) + n^2 √n menggunakan master theorem kasus 3.
(f). T (n) = T (√n) + 1 (petunjuk: substitusikan n = 2^m).
Solusi T (n) = T (√n) + 1 menggunakan master theorem kasus 2.
(g). T (n) = 2T (n – 1) + 1 (asumsikan T (1) = 1).
Kita tidak dapat menggunakan master theorem untuk kasus ini. Dengan evaluasi iteratif, kita memiliki
(h). T (n) = T (n – 1) + lg n (asumsikan T (1) = 1).
Dengan evaluasi iteratif, kita memiliki
Dengan sifat logaritma lg a + lg b = lg ab, diperoleh
Dengan aproksimasi Stirling, lg (n!) = Θ(n lg n). Akibatnya T (n) = 1 +Θ (n lg n) = Θ(n lg n)
(i). T (n) = T (n – 2) + 2 lg n (asumsikan T (0) = 2).
Karena paritas (genap-ganjil) dari n tidak berpengaruh pada nilai T (n) secara asimtotik, kita boleh mengasumsikan n genap. Dengan evaluasi iteratif, kita memiliki
(j). T (n) = √n T (√n) + 2013 n (petunjuk: misalkan T (n) = nS (n) dengan S (n) adalah fungsi yang asimtotik positif).
Misalkan T (n) = nS (n), maka T (√n) = √n S (√n). Akibatnya rekurensi pada soal setara dengan
Demikianlah contoh penggunaan master theorem dalam masalah rekurensi, semoga bermanfaat!
Science Booth 
Leave a Reply