21 votes 21 votes Let $T(n)$ be the function defined by $T(1) =1, \: T(n) = 2T (\lfloor \frac{n}{2} \rfloor ) + \sqrt{n}$ for $n \geq 2$. Which of the following statements is true? $T(n) = O \sqrt{n}$ $T(n)=O(n)$ $T(n) = O (\log n)$ None of the above Algorithms gate1997 algorithms recurrence-relation normal + – Kathleen asked Sep 29, 2014 edited Nov 7, 2017 by kenzou Kathleen 4.8k views answer comment Share Follow See all 13 Comments See all 13 13 Comments reply Swati Rauniyar commented Sep 7, 2017 reply Follow Share How to do it by recurrence tree method? 0 votes 0 votes ankitgupta.1729 commented Oct 10, 2018 reply Follow Share Recursion Tree Method :- Here , $\frac{n^{\frac{1}{2}}}{(\sqrt{2}-1 )} * [(2^{k})^{\frac{1}{2}}\sqrt{2} - 1]$ Now , put $k = lgn$ $\Rightarrow \frac{n^{\frac{1}{2}}}{(\sqrt{2}-1 )} * [(2^{lgn})^{\frac{1}{2}}\sqrt{2} - 1]$ $\Rightarrow \frac{n^{\frac{1}{2}}}{(\sqrt{2}-1 )} * [(n)^{\frac{1}{2}}\sqrt{2} - 1]$ So , here , $T(n) = \frac{\sqrt{2}}{(\sqrt{2}-1)}*n - \frac{n^{\frac{1}{2}}}{(\sqrt{2}-1)}$ $\Rightarrow T(n) \leqslant c*n , where \; c> 0$ So, $T(n) = O(n)$ 12 votes 12 votes srestha commented Jan 19, 2019 reply Follow Share @ankitgupta.1729 each level cost should be same in recursion tree right? https://gateoverflow.in/1325/gate2009-39 0 votes 0 votes ankitgupta.1729 commented Jan 19, 2019 reply Follow Share @srestha It depends on recurrence. Here it will not be same. In the given link, it will be same... 0 votes 0 votes srestha commented Jan 19, 2019 i edited by srestha Jan 19, 2019 reply Follow Share @ankitgupta.1729 why do u think cost of each level can be different? these lines from cormen, which clearly told cost of each level be same we add the costs across each level of the tree. The top level has total cost cn, the next level down has total cost cn/2+ c.n/2=cn, the level after that has total cost c.n/4+c.n/4+c.n/4+c.n/4= cn, and so on. In general, the level i below the top has 2i nodes, each contributing a cost of c.n=2i /, so that the ith level below the top has total cost $2^{i} c.(n/2^{i})= cn$. The bottom level has nnodes, each contributing a cost of c, for a total cost of cn. The total number of levels of the recursion tree in Figure 2.5 is $lg n + 1$, where n is the number of leaves, corresponding to the input size. An informal inductive argument justifies this claim. The base case occurs when n = 1, in which case the tree has only one level. Since lg 1 = 0, we have that lg n + 1 gives the correct number of levels. Now assume as an inductive hypothesis that the number of levels of a recursion tree with 2i leaves is $lg2^{i}+1$=i+1(since for any value of i, we have that $lg2^{i} = i$. Because we are assuming that the input size is a power of 2, the next input size to consider is 2iC1. A tree with $n = 2^{i}+1$ leaves has one more level than a tree with 2i leaves, and so the total number of levels is.$(i + 1)+ 1 = lg 2^{i+1 } + 1.$ To compute the total cost represented by the recurrence (2.2), we simply add up the costs of all the levels. The recursion tree has lg n C 1 levels, each costing cn, for a total cost of cn.(lg n + 1)=cn lg n + cn. Ignoring the low-order term and the constant c gives the desired result of $\theta(n lg n)$ 0 votes 0 votes ankitgupta.1729 commented Jan 19, 2019 reply Follow Share @srestha According to you what should be the same cost at each level here ? In cormen, it is given for a particular recurrence. 0 votes 0 votes srestha commented Jan 19, 2019 i edited by srestha Jan 19, 2019 reply Follow Share @ankitgupta.1729 I think it will be like this $\left ( \sqrt{n} \right )$ ---------------------1st level $\left ( \sqrt{n}/2 \right ),\left ( \sqrt{n}/2 \right )$--------------------in 2nd level $\left ( \sqrt{n}/2^{2} \right ),\left ( \sqrt{n}/2^{2} \right ),\left ( \sqrt{n}/2^{2} \right ),\left ( \sqrt{n}/2^{2} \right )$----------in 3rd level --------------------------------------------- In last level it will be $ \left ( \sqrt{n}/2^{log_{2}\sqrt{n}} \right ) ,\left ( \sqrt{n}/2^{log_{2}\sqrt{n}} \right ),........\left ( \sqrt{n}/2^{log_{2}\sqrt{n}} \right )$ And there are $\left (2^{ {log_{2}\sqrt{n}}} \right )$ level So, total time $\sqrt{n} .\left ( {2^{log_{2}\sqrt{n}}} \right ) =\Theta \left ( n \right )$ Is anything wrong here? 0 votes 0 votes ankitgupta.1729 commented Jan 19, 2019 reply Follow Share arey @srestha ma'am Aap kya kar rhi ho...Sorry , I am not getting you :( We have to replace n with n/2 each time, So, $\sqrt{n}$will be replaced with $\sqrt{n/2}$ not $\sqrt{n}/2$. If we have a recurrence as $T(n) = aT(\frac{n}{b}) + f(n)$ . Then cost at 1st level will be $f(n)$. Now on 2nd level, $T(n)$ calls $T(\frac{n}{b})$ 'a' times and cost of each call will be $f(\frac{n}{b})$. So, total cost at 2nd level will be a* $f(\frac{n}{b})$. Now like this we go level by level. 2 votes 2 votes srestha commented Jan 19, 2019 reply Follow Share but point is why u told replaced with $\sqrt{n/2}$ not $\sqrt{n}/2$?? In $f\left ( \frac{n}{b} \right )$ n and b two separate element ,right? they are not dependent 0 votes 0 votes ankitgupta.1729 commented Jan 19, 2019 reply Follow Share yes. n and b are separate element. If we have $f(x) = x^{2}$ then $f(\frac{x}{2}) = (\frac{x}{2})^{2}$. right ? Same thing here. Initially we have f(n)= $\sqrt{n}$ at 1st level for T(n). Now T(n) calls T(n/2) '2' times. So, for each T(n/2) , cost will be f(n/2)... So, $f(\frac{n}{2}) = (\frac{n}{2})^{1/2}$ , not $(n^{1/2})/2$. It is like Backward Substitution. $T(n) = 2T(n/2)+ \sqrt{n}$ $T(n)$ $=$ $2[2T(n/2^{2}) + (n/2)^{1/2})] + \sqrt{n} = 2^{2}T(n/2^{2}) + 2(\frac{n}{2})^{1/2} + n^{1/2}$ where $2(\frac{n}{2})^{1/2} + n^{1/2}$ is the cost of first 2 levels. 1 votes 1 votes jlimbasiya commented Dec 16, 2019 reply Follow Share @ankitgupta.1729 @srestha using floor or ceil make any difference in big O notation? Asking not for this question but in general scenario does floor or ceil make any change in overall complexity? 0 votes 0 votes ankitgupta.1729 commented Dec 24, 2019 reply Follow Share @jlimbasiya No. 0 votes 0 votes Kiyoshi commented Jun 9, 2021 reply Follow Share @ankitgupta.1729 You resolved all my doubts on solving the method by recursion tree method. Earlier I also think that cost of each level is same but when i tried to solve some question by taking this, few questions I’m not able to solve but now i understand what is the reason behind it...😊 2 votes 2 votes Please log in or register to add a comment.
Best answer 38 votes 38 votes Answer is $B$. using master method (case 1) where a = 2, b = 2 O(n1/2) < O(nlogba) O(n1/2) < O(nlog22) ankitrokdeonsns answered Oct 12, 2014 edited Jun 13, 2018 by Milicevic3306 ankitrokdeonsns comment Share Follow See all 4 Comments See all 4 4 Comments reply `JEET commented Jan 2, 2020 reply Follow Share Here $\mathrm{k \ngeq 0}$, then how you applied Master's theorem? 0 votes 0 votes `JEET commented Jan 2, 2020 reply Follow Share @Satbir Do you think this selected answer even correct? 0 votes 0 votes Satbir commented Jan 2, 2020 reply Follow Share k is 0.5 4 votes 4 votes `JEET commented Jan 2, 2020 reply Follow Share Ohh..that was a foolish mistake. Thanks. 0 votes 0 votes Please log in or register to add a comment.