News for hackers. Stuff that matters.
Re:An interesting data structure with search time O(sqrt n) by hvidgaard on Thursday December 03, 2015 @02:57AM (#10668413)
My point of view origins from the academic world, and the distinction absolutely matters, and it should matter in any theoretical discussion on the topic, otherwise we'll spend too much time arguing semantics, instead of just being clear.

> not strictly all self-balancing BSTs have all O(log n) operations.

You're right. You could have a self balancing tree that would simply guarantee it's height is n/2, but that entails that it's height is O(n), which, by most definitions mean that it's not self balancing. You want it to be at least O(n^c) for 0<c<1, in height.

Re:An interesting data structure with search time O(sqrt n) by Veedrac on Thursday December 03, 2015 @04:16AM (#10668645)
I'll put this under "agree to disagree". English is too vague to speak unambiguously in it all the time :P.