Question

If the number of steps required to solve a problem is O(n^k), then the problem is said to be solved in:

(a) non-polynomial time

(b) polynomial time

(c) infinite time

(d) none of the mentioned

I got this question in a national level competition.

Enquiry is from Problem Solvable in Polynomial Time in section Intractable Problems of Automata Theory

Answer 1

Right option is (b) polynomial time

The explanation is: Most of the operations like addition, subtraction, etc as well as computing functions including powers, square roots and logarithms can be performed in polynomial time. In the given question, n is the complexity of the input and k is some non negative integer.