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 Show 10 previous comments 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.