5 votes 5 votes How to solve above recurrence relation? $T(n) = \sqrt{2} T(n/2) + \sqrt{n}$ Algorithms algorithms recurrence-relation time-complexity + – anoop yadav 2 asked Jan 7, 2018 • edited Jan 8 by Hira Thakur anoop yadav 2 5.6k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
7 votes 7 votes $T(n) = \sqrt{2} T(\frac{n}{2}) + n^{\frac{1}{2}}$ .............. (1) $T(\frac{n}{2}) = \sqrt{2} T(\frac{n}{4}) + (\frac{n}{2})^{\frac{1}{2}}$ ..........(2) $T(\frac{n}{4}) = \sqrt{2} T(\frac{n}{8}) + (\frac{n}{4})^{\frac{1}{2}}$ ........(3) Resubstituting (3) in (2) $T(\frac{n}{2}) = \sqrt{2} [\sqrt{2} T(\frac{n}{8}) + (\frac{n}{4})^{\frac{1}{2}}] + (\frac{n}{2})^{\frac{1}{2}}$ $T(\frac{n}{2}) = 2T(\frac{n}{8}) + (\frac{n}{2})^{\frac{1}{2}} + (\frac{n}{2})^{\frac{1}{2}}$ ..........(4) Resubstituting (4) in (1) $T(n) = 2\sqrt{2}T(\frac{n}{8}) +n^{\frac{1}{2}} + n^{\frac{1}{2}} + n^{\frac{1}{2}}$ .........(5) Now $n = 2^k$ hence $k = logn$ Generalizing eq (5)... $T(n) = (\sqrt{2})^k * T(\frac{n}{2^k}) + k(n^\frac{1}{2})$ By solving the above equation, $T(n) = 2^{\frac{1}{2}logn} + logn (\sqrt{n})$ .........assuming $T(\frac{n}{2^k}) = T(1) = 1$ $T(n) = \sqrt{n} + logn(\sqrt{n})$ Hence $T(n) = \sqrt{n}(logn + 1)$ Ashwin Kulkarni answered Jan 7, 2018 • edited Jan 7, 2018 by Ashwin Kulkarni Ashwin Kulkarni comment Share Follow See all 2 Comments See all 2 2 Comments reply anoop yadav 2 commented Jan 8, 2018 reply Follow Share why we are getting different answer with master's formula. 0 votes 0 votes smsubham commented Feb 19, 2018 reply Follow Share @anoop Bcoz the question you asked is different from actual gate question. There it asked evaluates to (exact equation is needed) , buy masters theorem gives approximate asymptotic upper bound. https://gateoverflow.in/3354/gate2008-it-44 2 votes 2 votes Please log in or register to add a comment.
6 votes 6 votes From master theorem case 2 here a = √2 , b = 2 , k=1/2, p = 0 a = b^k which is true p > -1 So complexity is theta(n^(log a base to b) log^(p+1)n). theta(√n logn). Avdhesh Singh Rana answered Jan 7, 2018 Avdhesh Singh Rana comment Share Follow See all 2 Comments See all 2 2 Comments reply anoop yadav 2 commented Jan 7, 2018 reply Follow Share but the answer is sqrt(n) (logn+1). It is a question from made easy prev. year question [year 2008 2 marks] page no 370 qno 32. 0 votes 0 votes smsubham commented Feb 19, 2018 reply Follow Share #anoop Bcoz the question you asked is different from actual gate question. There it asked evaluates to (exact equation is needed) , buy masters theorem gives approximate asymptotic upper bound. https://gateoverflow.in/3354/gate2008-it-44 0 votes 0 votes Please log in or register to add a comment.