> O(log_b(n)) is the same as O(log n)
Not in every abstract model. See other reply.
Not in every abstract model. See other reply.
And in this case of O(sqrt i) memory access times, a binary tree and b-tree stay within a constant factor even as you vary b. (The reason is, the binary tree accesses that a single b-sized access replaces get exponentially more "local.")
There are models, like the cache oblivious model, where b is assumed to be a variable, so the model matters.
> a binary tree and b-tree stay within a constant factor even as you vary b.
it's not a constant factor if b is a variable. It's a factor of log b.
It's between 1/(sqrt(2)-1) and sqrt(2)/(sqrt(2)-1), depending on how full the b-tree nodes are.
sqrt(n)+sqrt(n/b)+sqrt(n/b^2)+... versus sqrt(n)+sqrt(n/2)+sqrt(n/4)+...
And since b-tree nodes can be half empty, there's a sqrt(2) uncertainty. (And of course there is no other memory overhead at all, none whatsoever.)
Or less generally: it takes sqrt(j) nanoseconds to dereference the pointer with value j, and parent nodes are at smaller addresses than their children.