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.
Edit: I vaguely remember hearing that heap allocation is unbounded in the worst case, but I'm really interested in the average/typical case.
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).
I don't know the specifics, but the "heap" (new/malloc/etc) use.. well.. a heap. So allocation from a heap should take no more than O(log n) where n is the available memory blocks.
The reason I say log n and not O(1) is because in the memory case you wouldn't want to just use the top of the heap, you'd want to find the smallest possibile piece of memory available that satisfies your request. Read more about heaps on wikipedia.
The time complexity for a heap allocator can be different on different systems, depending on what they might be optimizing for.
On desktop systems, the heap allocator probably uses a mixture of different strategies including caching recent allocations, lookaside lists for common allocation sizes, bins of memory chunks with certain size characteristics, etc. to try an keep allocation time down but also keep fragmentation manageable. See the notes for Doug Lea's malloc implementation for an overview of the various techniques that are used: http://g.oswego.edu/dl/html/malloc.html
For simpler systems, a strategy of first fit or best fit might be used, with the free blocks stored on a linked list (which would give a O(N) time with N being the number of free blocks). But a more sophisticated storage system such as an AVL tree might be used to be able to locate free blocks in O(log N) time (http://www.geocities.com/wkaras/heapmm/heapmm.html).
A realtime system might use an heap allocator like TLSF (Two-Level Segregate Fit), which has a O(1) allocation cost: http://rtportal.upv.es/rtmalloc/
Just check out how typical allocators work.
A bump-the-pointer allocator works in O(1), and it's a small '1' at that.
For a segregated-storage allocator, allocation of k bytes means "return the first block from List(n)" where List(n) is the list of blocks of n bytes where n >= k. It might find that List(n) is empty, so that a block from the next list (List(2n)) would have to be split with both resulting blocks of n bytes being put onto List(n), and this effect might ripple through all availlable sizes, making for a complexity of O(ns) where ns is the number of different sizes availlable, and ns = log (N) where N is the size of the largest block size availlable, so even that would be small. In most cases, especially after a number of blocks have been allocated and deallocated, complexity is O(1).
One of the things you have to realise when dealing with O notation is that it is often very important to understand what n is. If the n is something related to something you can control (eg: the number of elements in a list you want sorted) then it makes sense to look hard at it.
In most heap implementations, your n is the number of contiguous chunks of memory the manager is handling. This is decidedly not something typically under client control. The only n the client really has control over is the size of the chunk of memory she wants. Often this bears no relation to the amount of time the allocator takes. A large n could be as quickly allocated as a small n, or it might take much longer, or it might even be unservicable. All this could change for the same n depending on how previous allocations and deallocations from other clients came in. So really, unless you are implementing a heap, then the proper answer is that it is non-deterministic.
This is why hard realtime programmers try to avoid dynamic allocation (after startup).