Question

plz solve this
how to find time t( n/4)+t(3n/4)+cn​

Answer 1

Answer:

Either use recursive tree method to solve entire recurrence relation, or for simplicity ignore the T(n/4) part and solve following recurrence relation:

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

Recurrence tree for this recurrence relation will have logn base(4/3) levels and cost at each level is O(n).

if you add the costs from each level it will come to O(n*logn base(4/3)