An interesting data structure with search time O(sqrt n)

[Timon Gehr via Digitalmars-d]

On 12/02/2015 03:29 PM, Timon Gehr wrote:
> On 12/02/2015 12:26 PM, Timon Gehr wrote:
>> ...
>> ∑ᵢ[2≤i≤m]·log(i)·∑ₖ[0≤k≤⌊i/2⌋-1]·(2·k+1)
>> =
>> ∑ᵢ[2≤i≤m]·log(i)·⌊i/2⌋²
>>
>
> It should actually be (⌊i/2⌋-1)² here, but this does not change the
> asymptotics.

Oops. No, it was actually right. Sorry for the noise. :-)