Ah, in my context, N is the number of live allocated objects that the memory allocator knows about. If you use a data structure like a red-black tree to track the metadata, the work you do traversing and maintaining the tree will grow log N with the number of live allocated objects you're tracking. The radix tree specialization I presented is constant with respect to the number of live allocated objects.