Your book caches the best bid as a tick index. A cancel empties that level. Describe the update procedure, give its amortised cost over a run of m events, and construct the event sequence that makes it worst case linear in the tick range.

Your book caches the best bid as a tick index. A cancel empties that level. Describe the update procedure, give its amortised cost over a run of m events, and construct the event sequence that makes it worst case linear in the tick range.

Approach: The pointer only ever walks down after a cancel and jumps up on an add. Charge the downward walk against the adds that put liquidity there, then find the input that breaks the charging argument.

Walk the cached best bid index down until a non-empty level is found, which is O(1) amortised in the number of events and Theta(R) in the worst case for a tick range R. An add above the cached level sets the cache to that price in O(1). A cancel that empties the current level starts a downward scan, and each tick the pointer walk crosses was either occupied earlier and has since emptied, which can be charged to the add that occupied it, or was never occupied at all. The second kind is unbounded and is the breaking case: seed one order at tick 0, then repeatedly add and immediately cancel one order at tick R. Every cancel scans the entire empty range, so m events cost Theta(mR). A hierarchical bitmap over the ticks fixes it, with one bit per level summarised in 64-bit words, so the next occupied level below is found with a masked count of leading zeros per layer, giving O(log_{64} R) worst case and three layers covering a million ticks.

Follow-up: How would you extend the bitmap so that the total depth within k ticks of the touch is also available in constant time?

Key concepts: best bid, amortised cost, pointer walk, bitmap.