Documentation

Complexitylib.Models.RandomAccessMachine.Simulation.RegisterStore.Machine.EntryUpdate.BoundsInternal

Encoded-length sparse-update bounds -- proof internals #

The update controller reserves the slower of copy, replacement, and deletion at each iteration. With unary-marker decoding, each such reservation is still linear in the current entry and the instruction's query/replacement widths.

theorem Complexity.RAM.RegisterStore.Machine.entryUpdateTime_le_encoded_internal {n : } (tapes : EntryUpdateTapes n) (store : Store) (address newValue : ) :
entryUpdateTime tapes store address newValue 1000 * (encodedStoreLength store + (List.length store + 1) * (bitlen address + bitlen newValue + bitlen (List.length store) + 1) + 1)