title: Time complexity of memory allocation
body: <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>