45 votes 45 votes Consider the following two functions: $g_1(n) = \begin{cases} n^3 \text{ for } 0 \leq n \leq 10,000 \\ n^2 \text{ for } n > 10,000 \end{cases}$ $g_2(n) = \begin{cases} n \text{ for } 0 \leq n \leq 100 \\ n^3 \text{ for } n > 100 \end{cases}$ Which of the following is true? $g_1(n) \text{ is } O(g_2(n))$ $g_1(n) \text{ is } O(n^3)$ $g_2(n) \text{ is } O(g_1(n))$ $g_2(n) \text{ is } O(n)$ Algorithms gate1994 algorithms asymptotic-notation normal multiple-selects + – Kathleen asked Oct 4, 2014 • recategorized Apr 25, 2021 by Lakshman Bhaiya Kathleen 15.5k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
Best answer 71 votes 71 votes For asymptotic complexity, we assume sufficiently large $n$. So, $g_1(n) = n^2$ and $g_2(n) = n^3$. Growth rate of $g_1$ is less than that of $g_2$, i.e., $g_1(n) = O(g_2(n)).$ Options $A$ and $B$ are TRUE here. Arjun answered Oct 22, 2014 • edited Jun 24, 2018 by Shikha Mallick Arjun comment Share Follow See all 14 Comments See all 14 14 Comments reply Harit commented Jan 5, 2017 reply Follow Share i think only a is correct in second option they might be mentioning the time complexity of g1 itself which is not O(n^3) it is O(n^2) for n>=10000 i.e. high value of n 0 votes 0 votes rajan commented Jan 8, 2017 reply Follow Share @harit g1 value is (n^2) for n>=10000 so we can say g1 is asymptotically O(n^3) 0 votes 0 votes Syedarshadali commented Jan 7, 2018 reply Follow Share Sir please verify answer given by Avik10 0 votes 0 votes Sanjay Sharma commented Feb 22, 2018 reply Follow Share why not O(n^2) it will be asymptotically tighter then O(n^3) 0 votes 0 votes Arjun commented Feb 22, 2018 reply Follow Share $O(n^2)$ is also correct. 0 votes 0 votes rajatmyname commented Apr 6, 2018 reply Follow Share @Arjun Sir, I think option a is not correct because if you take an instance of the function at n=100, the given condition does not satisfy. So I think option b is only correct 0 votes 0 votes !KARAN commented Apr 15, 2018 reply Follow Share Arjun Sir, what if we are supposed to select only one option from the given choices. Would it be option A which is more suitable here. 0 votes 0 votes Arjun commented Apr 15, 2018 reply Follow Share See a question has only one answer whether you look from left or right. Before 2000 GATE had questions with multiple correct answers and you were given mark only if all are marked. 3 votes 3 votes mrinmoyh commented Jan 27, 2019 reply Follow Share for asymptotic notation we need n which is $n\geq n_{0}$ , here $n_{0}$ is 10,000.So $g_{1}\left ( n \right )$ & $g_{2}\left ( n \right )$ will be compared after 10,000 range for n $\geq$ 10,000. after 10,000 $g_{1}\left ( n \right ) = n^{2}$ & $g_{2}\left ( n \right ) = n^{3}$ i.e $g_{1}\left ( n \right )$ can never exceed $g_{2}\left ( n \right )$ in worst case. So, $g_{1}\left ( n \right )$ $\leq$ C. $g_{2}\left ( n \right )$ $\Rightarrow$ $g_{1}\left ( n \right )$ $= $O$\left ( g_{2} \left ( n \right )\right )$ $\Rightarrow$ $g_{1}\left ( n \right ) = O\left ( n^{3} \right )$ 14 votes 14 votes rishabhsharma commented Sep 7, 2020 reply Follow Share History is repeating now in 2021 ;-) 1 votes 1 votes vaibhavkedia968 commented Sep 9, 2020 reply Follow Share when were MSQs included for the first time? In 1988 maybe? :) 0 votes 0 votes Supriya Bhide commented Jan 28, 2021 reply Follow Share Won't C also be the answer along with A and B? 0 votes 0 votes rhl commented Sep 3, 2021 i edited by rhl May 30, 2023 reply Follow Share For sufficiently large n , $g_2 =n^3$ and $g_1 = n^2$, $n^2$ is not big oh of $n^3$. Hence, $g_2$ is not O($g_1$) 1 votes 1 votes KpKarenga_01 commented Dec 20, 2023 reply Follow Share Please explain in a manner way.! Why g2 is not O(g1)..?? 0 votes 0 votes Please log in or register to add a comment.
17 votes 17 votes The answer is given... prithatiti answered Jun 26, 2018 prithatiti comment Share Follow See all 2 Comments See all 2 2 Comments reply Vink7389 commented Apr 8, 2021 reply Follow Share What should be the value of n here so onwards n, g1(n) = O(g2(n)) always? 2 votes 2 votes prithatiti commented Nov 18, 2022 reply Follow Share I think 101 0 votes 0 votes Please log in or register to add a comment.
7 votes 7 votes Yes. Both (a) and (b) are correct. $n^{2}$ is $O(n^{3})$. gatecse answered Sep 20, 2014 • edited Oct 16, 2017 by kenzou gatecse comment Share Follow See all 2 Comments See all 2 2 Comments reply Marv Patel commented Sep 20, 2014 reply Follow Share I though so but when paper says select the correct(only one) choice then it creates doubt! 0 votes 0 votes air1ankit commented Nov 24, 2018 reply Follow Share question has only one answer whether you look from left or right. Before 2000 GATE had questions with multiple correct answers and you were given mark only if all are marked. 0 votes 0 votes Please log in or register to add a comment.
1 votes 1 votes Index Condition $g_{1}(n)$ $g_{2}(n)$ Time Complexity($B$) Time Complexity($A$) 1 $0 \leq n \leq 100$ $n^{3}$ $n$ $O(n^{3})$ $O(g^{2}(n))$ -- Fails 2 $101 \leq n \leq 10000$ $n^{3}$ $n^{3}$ $O(n^{3})$ $O(g^{2}(n))$ 3 $n \geq 10001$ $n^{2}$ $n^{3}$ $O(n^{3})$ $O(g^{2}(n))$ Thus the right option should be B Avik10 answered Jan 26, 2017 • edited Oct 16, 2017 by kenzou Avik10 comment Share Follow See all 4 Comments See all 4 4 Comments reply Syedarshadali commented Jan 7, 2018 reply Follow Share Make this best answer 0 votes 0 votes Arjun commented Feb 22, 2018 reply Follow Share This is wrong; big-O cares for only large $n$. 2 votes 2 votes lokeshsolanki17 commented May 10, 2020 reply Follow Share They are not asking about time complexity in question. They are asking about growth of functions g1(n) and g2(n). g1( n ) = O( g2(n) ) g1(n) <= c.g2(n) ; where n >= N and c > 0 here N value is 10,000. so option A is correct. because after N, g1(n) = n2, and g2(n) = n3 according to option B, g1( n ) = O(n3) is not tight but true because g1(n) belongs to set O(n3).so it is also true 1 votes 1 votes MohanK commented Dec 31, 2020 reply Follow Share @lokeshsolanki17, @Arjun Sir, what does it actually meant by “They are not asking about time complexity in question. They are asking about growth of functions g1(n) and g2(n)” ? Isn’t Time complexity inherently uses order of functions ? Is both Time complexity & growth of functions different ? 0 votes 0 votes Please log in or register to add a comment.