How to Solve Questions based on varients of Master Method

Question

T(n) =  a₁ T(n/b) + a₂ T(n/b)

eg T(n) = T(n/4) + T(3n/4) + n

Comments

 T1(n) =a₁ T(n/b₁) 

 T2(n) =a₂ T(n/b₂) 

T(n) = max( T1(n) + T2(n) ) .

for your example it should be $\Theta$( n ).

---

How did u get that O(n) . please explain the steps

---

T(n) = T(n/4) + n 

       = T(n/16) + n/4 + n

       = T(n/64)  + n/16 + n/4 + n.

 .

.

T(n) = T(1) + n/log₄ n + ...... +  n/16 + n/4 + n.

      =  n { 1 + 1/4 + 1/16 + ..... (log₄ n)th term )

      = O(n).

Similarly do for others...

---

just draw a recurrence tree.. it easy ...