> important distinction is that typically GC iterates over something (incurring a cost of O(N)) During _collection_ and N is size of live set, so divided by al

> important distinction is that typically GC iterates over something (incurring a cost of O(N)) 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-memory-allocation-using-jemalloc/480222803919/ 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.