Question: suppose there is a tree with number of child nodes increasing from 2 to 4 then 8 and so on.how can we write recurrence relation for such a tree.

Answer: 
* using subtitution method- T(n)=2T(n/2)+n
 =2[2T(n/2^2)+n/2]+n
 =2^2T(n/2^2)+n+n
 =2^2[2T(n/2^3)+n/2^2]+n+n
 =2^3T(n/2^3)+n+n+n

similarly subtituing k times-- we get

T(n)=2^k T(n/2^k)+nk
 the recursion will terminate when n/2^k=1
 k=log n base 2.

thus T(n)=2^log n(base2)+n(log n)
 =n+nlogn

thus the tight bound for the above recurrence relation will be 
 =n log N (base of log is 2)
Take a look at this [link](http://www.cs.duke.edu/~ola/ap/recurrence.html).

```
T(n) = 2 T(n/2) + O(n)         [the O(n) is for Combine]
T(1) = O(1) 

```