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

Re:An interesting data structure with search time O(sqrt n) by herewhere on Monday November 30, 2015 @07:30PM (#10652905)

if 4 <= N <= 16, then sqrt(N) <= log2(N) else sqrt(N) > log2(N)

So, in Big-O term, this only trying to optimize only small dataset (4 <= N <= 16).

[ Parent | on HN ]

Re:An interesting data structure with search time O(sqrt n) by teraflop on Monday November 30, 2015 @07:35PM (#10652926)

Big-O is only strictly meaningful in terms of asymptotic behavior; as soon as you start talking about specific values of N, you have to care about constant factors.

In this case, the constant factors will probably be quite different because the goal is to make better use of CPU cache.

[ Parent | on HN ]

Re:An interesting data structure with search time O(sqrt n) by spicyj on Monday November 30, 2015 @07:33PM (#10652920)

I mean, it depends on your data access patterns. Arrays are good for some things, trees are good for other things. Here's another option.

[ Parent | on HN ]