1.2k 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)$

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.
selected by
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
@harit  g1  value is (n^2) for n>=10000 so we can say g1  is asymptotically O(n^3)

why not O(n^2)  it will be asymptotically tighter  then O(n^3)
$O(n^2)$ is also correct.

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

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

edited by
This is wrong; big-O cares for only large $n$.