[reuben364]

Are all polynomial time algorithms implementable with primitive recursion? You would need to know the constant factor, right?

[adastra22]

In practice, yes. And for real world applications I know of, the depth of primitive recursion is small enough that loops can be fully unrolled. So e.g. bitcoin’s lack of a looping construct isn’t even a problem.