# Data structure for dynamic memory allocation

Think of the cell-probe model. Is there a data structure that can allocate contiguous chunks of memory of any length (like e.g. malloc in C), and free them, while avoiding memory segmentation, and executes every operation in worst-case deterministic O(log n) time where n is the total size of the memory?

By avoiding memory segmentation I mean that if the total number of free cells is F, then I should be able to allocate a contiguous segment of F cells or about F cells.

Even without the time bound, it is impossible to "avoid memory segmentation" unless you can move the allocated objects around, like in a compacting garbage collector. See Robson's "Bounds for Some Functions Concerning Dynamic Storage Allocation", which shows that allocating $m$ bytes in blocks of size between $n$ and $N$ requires $\Omega(m \log (N/n))$ bytes of memory.
• Not to my knowledge. You might want to post a new question about this, since it's so different from how malloc actually operates. One question you'll have to consider, for instance, is the question of what time cost you'll assign to the operation of moving a block of size $m$. You can read a bit about this in Bender et al.'s "Maintaining Arrays of Contiguous Objects". – jbapple Apr 8 '15 at 14:47
• Note that, if the cost of moving a block is linear in its size, and if blocks must be contiguous between calls to malloc/free, then algorithms taking $O(\log n)$ time in the worst case can never move large blocks once they are placed. As a result, patterns like the ones described by Robson may still be possible, thus forcing superlinear space usage. – jbapple Apr 8 '15 at 15:03