A new algorithm MaxPack for optimally packing furniture in a transportation cont

Question

A new algorithm MaxPack for optimally packing furniture in a transportation container claims to have worst case complexity O(n^2 logn), where n is the number of items to be packed.

From this, we can conclude that:

A. For every n, for every input of size n, MaxPack requires time proportional to n^2 log n.

B. For some n, for every input of size n, MaxPack requires time proportional to n^2 log n.

C. For every n, every input of size n can be solved by MaxPack within time proportional to n^2 log n.

D. For every n, there is an input of size n for which MaxPack requires time proportional to n^2 log n.

Explanation / Answer

Definition of O(g(n)) i.e. Big O is like for every n or for every large n, f(n) can be at most in order of g(n) or for every n, there is a constant c, such that f(n) is always equals to or less than c.g(n) .

From the above definition it is clear that given Big O means, that running time of algorithm can not extend more than a particular threashhold and it will be within that threshhold limit.

So best option for this is C. For every n, every input of size n can be solved by MaxPack within time proportional to n^2 log n.

So the MaxPack algorithm can have maximum running time in order of or propotional to n^2 log n, it cannot have running time more than that.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.