Solve recurence relation
for T(n) = 4T(n/2)+n
By master’s method​

1 thought on “Solve recurence relation<br />for T(n) = 4T(n/2)+n<br />By master’s method​”

1. Answer:

   T(n)=4T(n/2)+n2. For this recurrence, there are again a=4 subproblems, each dividing the input by b=2, but now the work done on each call is f(n)=n2.

   …

   The master method

   Case 1: f(n) is O(nlogba – ε). …

   Case 2: f(n) is Θ(nlogba). …

   Case 3: f(n) is Ω(nlogba + ε).

   Explanation:

   hope it’s help you

   Reply