edited by
594 views
3 votes
3 votes

a) T(n) = √n T(√n)  +  n

b) T(n) =  4T(n/2) + n2 √(2)

edited by

1 Answer

3 votes
3 votes

a) The first problem cannot be solved by Master's theorem as here coefficient of  T(n/b) is  variable which is sqrt(n)..Hence we need to use recursion tree approach or substitution method..

Here lets use recursion tree approach..

So here we find cost at each level which is given by f(n) which is f(n)  =  n here..

So in next level  , no of subproblems  =  √n

     Also size of subproblem as given in recurrence  =  √n

    Hence cost in second level     =   cost of each subproblem * number of subproblems in second level

                                                =   √n  *  √n

                                                =   n

   Hence cost in second level is same as that of cost in first level ..Likewise in next levels we can also check the costs which is same here for each level..

  Hence T(n)                             = Sum of costs at each level

                                               =  n + n +.........[ Number of terms will be decided by recursion tree depth which is found as : ]

For height of the tree , we need to see where the size of subproblem becomes 1 or any constant if the base case is given in the question..

So at 1st level , size of subproblem  =   n

    at 2nd level , size of subproblem  =  sqrt(n)  =  n1/2

   at  3rd level  , size of subproblem  =  sqrt(sqrt(n))  =  n1/2^2

   at  kth level , size of subproblem   =  n1/2^k

   Hence  

             n1/2^k    =  2 (say the constant  =  2)

==>      1/2k  .logn     =  1        [ Taking log both sides ]

==>      2k         =    logn

==>      k          =    log(logn)   [ Again taking log both sides ]

Hence recursion tree height    =  O(log(logn))

Hence  T(n)  =  cost at each level * recursion tree height

                   =  n * log(logn)

                   =  O(n log(logn))

Related questions

0 votes
0 votes
1 answer
1
gate_forum asked Jan 13, 2019
471 views
O(n)O(Log n)O(Log log n)none
0 votes
0 votes
1 answer
2
Manish Kumar 14 asked Jun 17, 2017
466 views
Time Complexity ofT(n) = 2T(n-1)+nby using substitution method
2 votes
2 votes
1 answer
3
0 votes
0 votes
1 answer
4
dhingrak asked Nov 26, 2014
392 views
Is sqrt(n)+ log n = omega(log n)? If yes then please explain why...?