Aspire's Library
A Place for Latest Exam wise Questions, Videos, Previous Year Papers,
Study Stuff for MCA Examinations - NIMCET
Study Stuff for MCA Examinations - NIMCET
Previous Year Question (PYQs)
The running time of an algorithm is $O(g(n))$ if and only if:
(A) its worst-case running time is $O(g(n))$ and its best-case running time is $\Omega(g(n))$.
(B) its worst-case running time is $\Omega(g(n))$ and its best-case running time is $O(g(n))$.
(C) $O(g(n))=\Omega(g(n))$.
(D) $o(g(n))\cap \omega(g(n))$ is non-empty.
Choose the correct answer from the options given below:
(A) its worst-case running time is $O(g(n))$ and its best-case running time is $\Omega(g(n))$.
(B) its worst-case running time is $\Omega(g(n))$ and its best-case running time is $O(g(n))$.
(C) $O(g(n))=\Omega(g(n))$.
(D) $o(g(n))\cap \omega(g(n))$ is non-empty.
Choose the correct answer from the options given below:
Solution
For an algorithm to have tight running time $\Theta(g(n))$, worst-case should be $O(g(n))$ and best-case should be $\Omega(g(n))$.This condition is given in statement A.
Statement B reverses the required bounds.
Statement C is false because $O(g(n))$ and $\Omega(g(n))$ are not always equal.
Statement D is false because a function cannot be both smaller order and larger order than the same $g(n)$.
Online Test Series, Information About Examination,
Syllabus, Notification
and More.
View More
Online Test Series, Information About Examination,
Syllabus, Notification
and More.
View More
Ask Your Question or Put Your Review.
