It perfectly feasible to pre-allocate the bitstrings to their largest possible size

That's cheating, in some sense.

If you consider all limitation of real machines, you will find that perl can only ever handle a fixed, finite amount of RAM (if the pointers are 64 bit, it's 2**64), every list is limited by that, so every of the mentioned algorithms runs in O(1). Just with a very big constant.

That's why you usually rely on the model of an ideal machines (works with bigints, and arbitrarily much RAM) for the run time analysis.