The main difference here is the goal. "O(1)" algorithm often means efficient algorithm out there in the field, but this paper has absolutely no intention of making anything efficient.

People are wrong with that (1) O(1)=fast/efficient (2) I'm arguing over the definition of "constant-time".