Time complexity of memory allocation
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.
Solution 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).
Solution 2:
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.oocities.org/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://www.gii.upv.es/tlsf/
Solution 3:
Just two remarks:
TLSF is O(1) in the sense that is has not a single loop; and manages up to 2Gb. Although it is really hard to believe, just check the code.
It is not true that the "best fit" policy (find the tight block) is the most suitable to achieve small fragmentation. It is far from trivial to demonstrate this claim, in fact it has not been formally proven but there are lot of evidences that go in that direction. (nice research topic).
Solution 4:
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).