Master's Theorem (Module - 2) J(n) = at (n/b)+f(n)==0 Cif F(n) = O(nd), d±0 i T(n) = O(nd if as69 ii) T(n) = O(nd logn) if a = b. iii) T(n) = O(nlog&b) if a>bd Q. Solve by using Master's Theorem ⇒T(R) = HT (7/2)+九 Ans: Compare with T(n) = a(n)+f(n) (2) = (11) a = 4; b = 2, f(n) =)几、do Assume f(n) = n² prod 1 f(n)(n)=(7) 1-39 1 1 It satisfie's the spectation Condiben ayba 1(n) (nlogy) = O(nlog202) = (n²) Q.2) (n) = GT()+n² Anc(n) = 3T (₂)+n² 2 Compare with. T(n) = at (n)+f(n) - a = 3, b=2, f(n) = n d = 2 (the power ofn) f(n)= (22) (PA) CANT It Bativefires the condition a bk, (n) (nlogab) a) if P<-1, (n) = (n) = (nlog) B) if P=-1/T(n) = (logo) c) if p >-1, (n) (nlogo log Pth) iii) if a sbk and a) if pro, T(n)=(nk) b) if pro, +(n) = O(nk logn) 0 Q.T(n) = 2T (n) + n log n K = 1, P=1 Satisfying Ind case then the case (C) T(n) = O(nlogo-lognets) (path = O(nlog-loginti) = O(nlogon) Q. T(n) = √2T()+logn a = √2, b=8 K=1, Pel <2' 1-4142 sahsfied a bk. 80, god Condition is Then, Here (b) case is followed. P7=0 10 thin (n) = (login) T = O(logn)