From Shift, Pop, Unshift and Push with Impunity!:

One consequence of perl's list implementation is that queues implemented using perl lists end up "creeping forward" through the preallocated array space leading to reallocations even though the queue itself may never contain many elements. In comparison, a stack implemented with a perl list will only require reallocations as the list grows larger. However, perl is smartly coded because the use of lists as queues was anticipated. Consequently, these queue-type reallocations have a negligible impact on performance. In benchmarked tests, queue access of a list (using repeated push/shift operations) is nearly as fast as stack access to a list (using repeated push/pop operations).

I read this to mean that while naive implementation would have yielded O(N²), perl is smart enough that the exponent drops (closer) to O(N). Is this incorrect?

Also, it seems like O(N²) on splice is a worst case, where best case (either all or no deletions) would be O(N), leading me to think it'd be closer to O(N log N) in practice.

The crux of my question though was supposed to be about the constant in front of the memory term, particularly as all scale equivalently in memory.