Algorithms

Question 39

Consider the following two functions:

Which of the following is true?

A	g₁(n) is O(g₂(n))
B	g₁ (n) is O(³)
C	g₂ (n) is O(g₁ (n))
D	g₂ (n) is O(n)
E	Both A and B

AlgorithmsAsymptotic-NotationsGATE 1994

Question 39 Explanation:

In asymptotic complexity, we assume sufficiently large n. So, g₁(n) = n² and g₂(n) = n³.
Growth rate of g₁ is less than that of g₂ i.e., g₁(n) = O(g₂(n)) = O(n).

Correct Answer: E

Question 39 Explanation:

In asymptotic complexity, we assume sufficiently large n. So, g₁(n) = n² and g₂(n) = n³.
Growth rate of g₁ is less than that of g₂ i.e., g₁(n) = O(g₂(n)) = O(n).