Show the approach

Question

Recurrence:

$T\left ( n \right )\leq T\left ( \frac{n}{5} \right )+T\left ( \frac{7n}{10} \right )+\Theta \left ( n \right )$

Answer 1

Using recursion tree approach , we find cost at each level which is decided by f(n) and compare the cost of the current level with the previous level..

a) If the cost keeps on increasing with each level , then we have to evaluate the series as a whole which is normally a geometric progression.

b) If the cost at each level is constant , then time complexity is simply the cost at eah level * No of levels of recursion tree

c) If the cost at each level decreases , then it becomes the case of decreasing G.P. normally and hence the sum will be f(n) itself..

So in the given recurrence relation :  T(n) <=  T(n/5) + T(7n/10) + θ(n)

So cost in 1st level  =  f(n)  = cn for some constant c..Let us take c = 1 for simplicity.Hence cost becomes = n 

Cost in 2nd level    =  f(n)   = n/5 + 7n/10  =  9n/10

So we can see cost in 2nd level  < cost in 1st level.Hence it is the 3rd case according to the cases which are mentioned above..

Hence time complexity  =  n + 9n/10 + (9/10)²n  +  .............

                                   =  n(1 + (9/10) + (9/10)² + .......)

                                   =  kn   =  O(n)