33 votes 33 votes Suppose $T(n) =2T (\frac{n}{2}) + n$, $T(0) = T(1) =1$ Which one of the following is FALSE? $T(n)=O(n^2)$ $T(n)=\Theta(n \log n)$ $T(n)=\Omega(n^2)$ $T(n)=O(n \log n)$ Algorithms gatecse-2005 algorithms asymptotic-notation recurrence-relation normal + – Kathleen asked Sep 22, 2014 edited Oct 17, 2017 by kenzou Kathleen 9.6k views answer comment Share Follow See all 3 Comments See all 3 3 Comments reply Manu Thakur commented Dec 21, 2017 reply Follow Share It is the recurrence relation of $Merge-Sort$. The time complexity of merge sort is $Θ(nlogn)$. The option (C) is false! 14 votes 14 votes Shubhdwivedi commented Sep 17, 2021 reply Follow Share In option c if it would have been given omega (n) then will it be right? 0 votes 0 votes Abhishek Rauthan commented Jan 5, 2023 reply Follow Share yes @Shubhdwivedi 0 votes 0 votes Please log in or register to add a comment.
Best answer 42 votes 42 votes Applying Masters theorem, $T(n) = \Theta (n \log n)$ So, it cannot be $\Omega(n^2)$. Hence, answer is (C). shree answered Jan 26, 2015 edited Jun 24, 2018 by Shikha Mallick shree comment Share Follow See all 12 Comments See all 12 12 Comments reply srestha commented Sep 10, 2016 reply Follow Share Why not D)? –1 votes –1 votes vijaycs commented Sep 10, 2016 reply Follow Share here we are asked to choose false option, so option D is not false here. You can think of merge sort algorithm which has same type of algo and its time complexity is O(nlog n). 2 votes 2 votes Arjun commented Sep 10, 2016 reply Follow Share $\Theta \implies O \wedge \Omega$. So, D is true. 16 votes 16 votes srestha commented Sep 11, 2016 reply Follow Share C) will true for $\Omega (n) and \Omega (n log n)$ in both cases, rt? 0 votes 0 votes cse23 commented Sep 11, 2016 reply Follow Share theta(nlogn) means our value can be >= as well <= of nlogn T(n) is upper as well lower bounded by nlogn. (A) is O(n2) so value of T(n) is less than n2 which satisfy lower bounded by nlogn (C) is omega(n2) means T(n)>= n2 which is not possible because it is upper bounded by nlogn (D) tells that it is less than <=nlogn which is fine 13 votes 13 votes focus _GATE commented Nov 26, 2016 reply Follow Share yes srestha lower bound will be true for both Ω(n)andΩ(nlogn). 0 votes 0 votes focus _GATE commented Nov 26, 2016 reply Follow Share i have doubt here when we solve the value of T(n) using master theorem we have used ⊝( nlogn) why we use theta here?? why not any other notation ?? 1 votes 1 votes saurabh rai commented Dec 20, 2016 reply Follow Share @for better understanding of master theorem see proofof master theorem in cormen.... 1 votes 1 votes Arjun commented Dec 21, 2016 reply Follow Share @Kunal $\Theta$ implies $O$ and $\Omega$. And Master theorem is for $\Theta$. We can instead use $O$ or $\Omega$ also as both are implied by $\Theta$ but in any case the meaning of these must be known correctly before using. 7 votes 7 votes focus _GATE commented Dec 21, 2016 reply Follow Share got now thanks sir 1 votes 1 votes Shubham Aggarwal commented Nov 7, 2018 reply Follow Share arujun sir it means theta determine big oh and omega. Or theta equal to big oh and omega. ??? 0 votes 0 votes CSHuB commented Dec 31, 2019 reply Follow Share @satbir Is the comment made by @cse23 correct? 0 votes 0 votes Please log in or register to add a comment.
1 votes 1 votes watch first 20 min, you will understand all about notations https://www.youtube.com/watch?v=P7frcB_-g4w mohit kumar 5 answered Oct 18, 2017 mohit kumar 5 comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes If you are not getting how Master theorem works step by step, you can refer this blog post: https://devsathish.wordpress.com/2012/01/19/master-theorem-with-examples/ P.S. Not mine. mayurp7 answered Aug 22, 2017 mayurp7 comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes Apply masters theorem to the above example, a=2, b=2, k=1, p=0. The recurrence relation result will be O(nlogn). varunrajarathnam answered Aug 8, 2020 varunrajarathnam comment Share Follow See all 0 reply Please log in or register to add a comment.