Introduction to design and analysis of algorithms, third edition. Problem 11.3.2

Question

Introduction to design and analysis of algorithms, third edition. Problem 11.3.2

A certain problem can be solved by an algorithm whose running time is in O(nlog2n). Which of the following assertions is true?

A. The problem is tractable.

B. The problem is intractable

C. Impossible to tell

I know that tractable means that the problem can be solved in polynomial time, and intractable is not. I presume since this is in log time this problem is intractable. So the answer would be B since we can tell from the equation. I would like to verify this, thanks.

Explanation / Answer

This comes under Tractable as  O(nlog2n) is the complexity which means that algorithm runs in the efficient time and you can calculate the time as well.

let us suppose n =8

for that O(nlog2n) = 8*3=24.

Hence you can calculate for any value of n.

Hence it is tractable

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

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