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