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)
For a knapsack problem, $P$ and $W$ are profits and weights for a set of $7$ items as given below:
$P={9,5,2,7,6,16,9}$
$W={2,5,6,11,1,9,3}$
If new item $(P=5,W=2)$ is added to the list, total items is $8$ and capacity is $25$, then the best-case time of fractional knapsack for this case is ______
If new item $(P=5,W=2)$ is added to the list, total items is $8$ and capacity is $25$, then the best-case time of fractional knapsack for this case is ______
Solution
For fractional knapsack, if items are already arranged according to profit by weight ratio, then best-case selection can be done in linear time.
Here, total items are:
$n=8$
So, best-case time complexity is:
$O(n)=O(8)$
Correct option is:
$\boxed{(a)\ O(8)}$
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.
