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 had been asked this question in a national level competition.

My doubt is from Problem Solvable in Polynomial Time in division Intractable Problems of Automata Theory

Answer 1

The correct answer is:

(b) polynomial time

Explanation: If the number of steps required to solve a problem is O(nk)O(n^k)O(nk), where $k$ is a constant, then the problem is said to be solved in polynomial time. The term "polynomial time" refers to algorithms whose time complexity can be expressed as a polynomial function of the input size $n$, such as O(n2)O(n^2)O(n2), O(n3)O(n^3)O(n3), etc.

• Non-polynomial time: This refers to problems that require more than polynomial time to solve, such as exponential time complexities O(2n)O(2^n)O(2n).
• Infinite time: This is not a standard term in computational complexity theory.
• None of the mentioned: Since the correct option is "polynomial time," this choice is not correct.

Thus, if the time complexity is O(nk)O(n^k)O(nk), it is polynomial time.