Question

The worst-case efficiency of solving a problem in polynomial time is?

(a) O(p(n))

(b) O(p( n log n))

(c) O(p(n^2))

(d) O(p(m log n))

I had been asked this question by my college director while I was bunking the class.

Asked question is from Checksum, Complexity Classes & NP Complete Problems in chapter Checksum, Complexity Classes & NP Complete Problems of Data Structures & Algorithms II

Answer 1

Correct answer is (a) O(p(n))

The explanation is: The worst-case efficiency of solving an problem in polynomial time is O(p(n)) where p(n) is the polynomial time of input size.