[8organicbits]

Then perhaps I'm misunderstanding you. When N is *sufficiently* large, I think we all agree that you'll prefer an algorithm with better big-O.

When N is small, the asymptotic behavior is irrelevant and that's easy to show. Let's say we're comparing a O(N) algorithm to a O(N^2) algorithm, but each operation of the O(N) is 1000x more expensive. The O(N^2) algorithm is preferred as long as N < 1000. Choosing the O(N) algorithm will hurt performance in those situations. Real world examples like single-byte-writes causing full pages to be re-written on SSDs shows this isn't just a mathematical curiosity.

Without benchmarks, analysis of big-O behaviors, usage patterns, and known data size I'd (personally) avoid guessing the performance of Atree in an application.

Are you saying something different? It sounds like you have much more SIMD experience than I do and I'm always happy to learn something new.

https://www.wolframalpha.com/input?i=n*1000+%3D+n%5E2