Which option best describes the asymptotic relationship between g1(n) and…
1998
Which option best describes the asymptotic relationship between g1(n) and g2(n)?
Given functions:
g1(n):
n3 for 0 ≤ n ≤ 10,000
n2 for n ≥ 10,000
g2(n):
n for 0 ≤ n ≤ 100
n3 for n > 100
Answer: A. g1(n) is O(g2(n)) — Asymptotic comparison: For sufficiently large n, g1(n) = n2. For sufficiently large n, g2(n) = n3. n2 grows slower than n3, so g1(n) is O(g2(n)). g1(n) is…
- A.
g1(n) is O(g2(n))
- B.
g1(n) is O(n3)
- C.
g2(n) is O(g1(n))
- D.
g2(n) is O(n)
Attempted by 250 students.
Show answer & explanation
Correct answer: A
Asymptotic comparison:
For sufficiently large n, g1(n) = n2.
For sufficiently large n, g2(n) = n3.
n2 grows slower than n3, so g1(n) is O(g2(n)).
g1(n) is also O(n3) as a broad upper bound, but that does not best compare the two given functions.
Final answer: Option A
A video solution is available for this question — log in and enroll to watch it.
Explore the full course: Iocl Engineers Officers Grade A Paper 2