An Estimate of the Store Size Necessary for Dynamic Storage Allocation
John Michael Robson · Journal of the ACM · 1971
Dynamic storage allocation using fixed blocks is usually inefficient in its use of store.The amount of store needed depends on the allocation strategy used.It is proved that for any strategy the amount of store needed is bounded below by a function which rises logarithmically with the size of blocks used.A certain strategy is shown to exceed this bound by a factor of at most 13/4.The exact amount of store needed is found for the case when blocks have sizes 1 and 2 only.