But my original point was just that it's interesting that there is an extra step at all in the C++ case, where we tend to think of collection as happening "for free". It has a constant-time overhead, which is not the same as zero overhead.
During _collection_ and N is size of live set, so divided by allocation the cost is amortized and can safely considered as O(1) much like appending a dynamic array where costly O(N) resize is amortized over N appends.
Typically GCs allocate via bump a pointer allocation which is actually faster then what pretty much all of libc malloc implementations would do.
> C++ case iterates over nothing (incurring a cost of O(1)).
Not quite, take a look at jemalloc paper for instance:
https://www.facebook.com/notes/facebook-engineering/scalable...
A lookup to get the metadata for this specific allocation could be anything from O(1) to O(lgN) depending on size and malloc strategy.