The Gateway to Computer Science Excellence
+25 votes
3.3k views

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 \geq 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?

  1. $g_1(n) \text{ is } O(g_2(n))$

  2. $g_1(n) \text{ is } O(n^3)$

  3. $g_2(n) \text{ is } O(g_1(n))$

  4. $g_2(n) \text{ is } O(n)$

in Algorithms by Veteran | 3.3k views

5 Answers

+44 votes
Best answer
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.
by Veteran
edited by
0
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
@harit  g1  value is (n^2) for n>=10000 so we can say g1  is asymptotically O(n^3)
0

Sir please verify answer given by  Avik10 

0
why not O(n^2)  it will be asymptotically tighter  then O(n^3)
0
$O(n^2)$ is also correct.
0
@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
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.
+2
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.
+4
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 )$
+11 votes

The answer is given...Here is the answer...

by Junior
+7 votes

Yes. Both (a) and (b) are correct. $n^{2}$ is $O(n^{3})$.

by Boss
edited by
0
I though so but when paper says select the correct(only one) choice then it creates doubt!
0
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.
+1 vote

Hope this helps :)

by Active
0 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

by Junior
edited by
0
Make this best answer
+1
This is wrong; big-O cares for only large $n$.
0
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

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,223 questions
59,811 answers
201,020 comments
118,087 users