plz solve this
how to find time t( n/4)+t(3n/4)+cn
Answers
Answered by
0
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)
Similar questions