Question

The number of leaf nodes in the recurrence tree of the recurence

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

Answer 1

i think exact number of leaf nodes is somewhat hard here. what we can do is can find upper bound and lower bound .

upperbound - the greater function is n/2. so if we draw the tree of the function it will half full . for upperbound consider it to be fuly filled . and as n/2 is going till the end .

height of tree will be logn base 2 . taking only n/2 in consideration.
no . of leafs at height h =2^logn base 2 which will be equal to n.

lower bound . consider it fully filled by taking n/4 in consideration.

so no of leafs in that case = 2^logn base 4

n^0.5
no of nodes will be betwen n^0.5 to n .

Comments

actually i was not finding the actual no of leaves rather i was interested in the bound which u have stated perfectly. means if we have a recurrence T(n) = a T(n/b) +f(n) then the height of the tree will be log n base b. and no of leaves will be a^(log n base b) right?? same as master method's proof?? in this question we had two recursive function whose growth was different so we cant calculate the height and width accurately as one tree ends before the other right??

---

yes. it's the same method by which we find complexity of such a function. giving exact number is somewhat very tough. we can take the bound as this . if solved mark as best answer.

---

thanks