Aspire's Library

A Place for Latest Exam wise Questions, Videos, Previous Year Papers,
Study Stuff for MCA Examinations - NIMCET

Previous Year Question (PYQs)



Assume that $f(n)$ and $g(n)$ are asymptotically positive. Which of the following is correct?





Solution

If $f(n)=O(g(n))$ and $g(n)=O(h(n))$, then by transitivity:

$f(n)=O(h(n))$

But option says:

$f(n)=\omega(h(n))$

So, option (a) is incorrect.

Check option (b):

If $f(n)=\Omega(g(n))$ and $g(n)=\Omega(h(n))$, then:

$f(n)=\Omega(h(n))$

But option says:

$f(n)=O(h(n))$

So, option (b) is incorrect.

Check option (c):

If $f(n)=o(g(n))$, then $f(n)$ grows strictly slower than $g(n)$.

If $g(n)=o(h(n))$, then $g(n)$ grows strictly slower than $h(n)$.

Therefore, $f(n)$ also grows strictly slower than $h(n)$.

So,

$f(n)=o(h(n))$

Thus, option (c) is correct.

Check option (d):

If $f(n)=\omega(g(n))$ and $g(n)=\omega(h(n))$, then:

$f(n)=\omega(h(n))$

Since $\omega(h(n))$ is stronger than $\Omega(h(n))$, option (d) is also mathematically correct.

Therefore, mathematically both option (c) and option (d) are correct.

If the exam expects only one answer, then the question has ambiguity.


Online Test Series,
Information About Examination,
Syllabus, Notification
and More.

Click Here to
View More


Online Test Series,
Information About Examination,
Syllabus, Notification
and More.

Click Here to
View More

Ask Your Question or Put Your Review.

loading...