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

[Timon Gehr via Digitalmars-d]

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.