I am reading about P and NP and looking at the reduction of a Rudrata/Hamiltonian path to a Rudrata cycle. I think adding an extra node and 2 edges connecting the start, s and the target, t is O(1) time as this doesn't depend on the size of the graph. Algorithms by Dasgupta et al. says that the pre and post processing steps take polynomial time.

One last detail, crucial but typically easy to check, is that the pre- and postprocessing functions take time polynomial in the size of the instance (G, s, t).

This makes me think that O(1) is polynomial time. Is this incorrect?


1 Answer 1


Yes, any constant is a polynomial of degree zero.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.