1
$\begingroup$

Is a computer with infinite memory and infinite word size a Truing machine equivalent (in the sense that polynomial time remains polynomial time and exponential time remains exponential time) if we allow constant-time linked link element insertion (at the beginning of the list)?

I doubt this because element insertion requires memory allocation and allocation is usually not a constant-time operation.

$\endgroup$
1
  • $\begingroup$ gii.upv.es/tlsf claims constant-time memory allocation. But does that solution scale for systems of infinite memory (and infinite word size)? $\endgroup$ – porton Apr 16 at 10:27
0
$\begingroup$

Oh, I've found an $O(1)$ allocation strategy:

Because our memory is infinite, we may never deallocate: Just add memory at the end of the used space by incrementing a pointer.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.