On the subject of an XML parser

[tsbockman]

On Monday, 3 October 2022 at 07:28:46 UTC, tsbockman wrote:
> On Monday, 12 September 2022 at 09:29:11 UTC, Ali Çehreli wrote:
>> I realized that it is still O(1) because the seemingly 
>> unnecessarily grabbed elements would still count as 
>> "amortized" because they are readily available at O(1) for 
>> consumption of both this range and all its .save'd ranges.
>
> I believe it's actually **O(log(n))** amortized because 
> `CircularBlocks.addExistingBlock_` will reallocate `blocks` and 
> move the contents over to the new address, an **O(n)** 
> operation, for every **O(log(n))** accesses to `ElementCache`.
>
> (This extra **O(log(n))** factor is typical for 
> [Appender](https://dlang.org/phobos/std_array.html#Appender)-like systems.)

Nevermind - I forgot that the **n** when moving the old contents 
over is actually a different variable each time, whose average 
value is **O(n / log(n))**, which makes the whole thing reduce to 
amortized **O(1)** time per element, as you claimed.