@JBM What I meant was that if you consider the numbers are written on a bounded number of bits, then they are themselves bounded, so the actual complexity can only be O(1). But indeed in practice everybody understands why we say O(N) here.

@eulerscheZahl Indeed ~~(even though it goes up to the next power of 2)~~.