You can make a model where the presented algorithm runs in O(1) time, for example a transdichotomous model. However those models have very unintuitive consequen

You can make a model where the presented algorithm runs in O(1) time, for example a transdichotomous model. However those models have very unintuitive consequences (for example, the O(n log n) bound for sorting doesn't hold any longer!), which is what I was hinting to with my "big O is broken" remark. You are absolutely right that it can't be done on a fixed-width register machine, though. Generally speaking, most papers assume arithmetic is O(1) time and integers fit in O(1) space because keeping track of the actual time and space of integer arithmetic gets unwieldy very quickly. But this model is super broken: if arbitrary arithmetic can be performed in O(1) then P = PSPACE. The "gentlemen's agreement" assumption is that operations that make numbers grow too big are forbidden. I don't know much about this stuff (I'm way out of my depth as a matter of fact), but I'm glad I could be useful :)