T(n) = a1 T(n/b) + a2 T(n/b) eg T(n) = T(n/4) + T(3n/4) + n
T1(n) =a1 T(n/b1)
T2(n) =a2 T(n/b2)
T(n) = max( T1(n) + T2(n) ) .
for your example it should be $\Theta$( n ).
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/log4 n + ...... + n/16 + n/4 + n.
= n { 1 + 1/4 + 1/16 + ..... (log4 n)th term )
= O(n).
Similarly do for others...
64.3k questions
77.9k answers
243k comments
79.6k users