In the recurrence tree method, we make a tree with the help of the recurrence equation.
If equation is T(n) = a T(n/b) + C, then we make a recurrence tree
Example 1 Draw the recurrence relation T(n) = 2T(n/2) + n
Compiling Time = 2T(n/2) Running Time = n 
After summation all the operations = n + n + n + ... + n [log n time]
= n.logn
= O(n.logn) is the Ans
Example 2 Draw the recurrence relation T(n) = 2T(n/2) + n^2
Compiling Time = 2T(n/2) Running Time = n^2
After summation all the operations = n^2 + (n^2)/2 + (n^2)/4 + (n^2)/8 + .... + 1
= n^2 [ 1 + 1/2 + 1/4 + 1/8 + .... + 1/n^2]
This is a G.P. Series with r = 1/2
= n^2 [ 1 / (1 - 1/2) ]
= O(n^2) is the Ans.
Example 3 Draw the recurrence relation T(n) = T(n/3) + T(2n/3) + n
Compiling Time = T(n/3) + T(2n/3) Running Time = n
After summation all the operations = n + n + n + ... + n [log n time]
= n.logn
= O(n.logn) is the Ans
0 Comments