<p>What is the time complexity of dynamic memory allocation using new, malloc, etc.?  I know very little about how memory allocators are implemented, but I assume the answer is that it depends on the implementation.   Therefore, please answer for some of the more common cases/implementations.</p>

<p>Edit:
I vaguely remember hearing that heap allocation is unbounded in the worst case, but I'm really interested in the average/typical case.</p>

I would think it would generally be O(n) where n is the number of available memory blocks (since you have to scan the available memory blocks to find a suitable one).
Having said that, I've seen optimizations that can make it faster, specifically maintaining multiple lists of available blocks depending on their size ranges (so blocks less than 1k are in one list, blocks from 1k to 10k are in another list and so on).
This is still O(n) however, just with a smaller n.
I'd be interested in seeing your source that there's a heap allocation that's unbounded (if, by that, you mean it could take forever).