> A simple example of constant-time within this definition, as well as why constant-time does not mean O(1) in this context, is that of a comparator: This is i

> A simple example of constant-time within this definition, as well as why constant-time does not mean O(1) in this context, is that of a comparator: This is incorrect. The paper explicitly uses "constant time" in the sense of O(1). You can see this listed throughout the paper, in various complexity analyses, beginning from Section 2.