0
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

Yes, any constant is a polynomial of degree zero.

Improve this answer
$\endgroup$
3

Your Answer

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

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