GATE CSE 1994 | Question: 1.23

Question

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?

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

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

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

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

Comments

Fastest GATE Trick

 

Ignore the finite initial range.

Look only at what happens for large n.

g₁(n) ≈ n²   (for n > 10000)
g₂(n) ≈ n³   (for n > 100)

 

So asymptotically:

                               g1​(n)=Θ(n²) 

                               g2(n)=Θ(n³)

---

Option A

 

Check:

         n² = O(n³)

✅ True

---

Option B

 

  Since, n² = O(n³)

✅ True

---

Option C

 

Check:

         n³=O(n²)

❌ False

---

Option D

 

Check:

         n³ =O(n)

❌ False

Answer 1

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.

Comments

@jeets if it is less then n^2 then it is less then any function bigger then n^2
so n^3 is correct 

---

How option B is correct even though Big-O cares about largest n after 10,000 till infinity it is n^2 ryt?

---

Big-O means all upper bounds ( both tight and non tight) so if O(n^2) is correct then so is O(n^3).

 

Answer 2

The answer is given...

Comments

What should be the value of n here so onwards n, g1(n) = O(g2(n)) always?

---

I think 101

Answer 3

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

Comments

I though so but when paper says select the correct(only one) choice then it creates doubt!

---

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.

Answer 4

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

Comments

Make this best answer

---

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

---

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

---

@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 ?

 

Answer 5

In asymptotic complexity, we assume sufficiently large n. So, g1(n) = n2 and g2(n) = n3.
Growth rate of g1 is less than that of g2 i.e., g1(n) = O(g2(n)) = O(n).

Both A and B are True

Answer 6

For asymptotic analysis, we assume sufficiently large value of n i.e n>10,000.

For this case, g1(n) = n^2, g2(n) = n^3

clearly, g1(n) = O(g2(n)) = O(n^3).