3 ms·
> It has nothing to do with the model and is just a question of whether b is a variable in the big O notation. There are models, like the cache oblivious model
by DanWaterworth 10y ago
> It has nothing to do with the model and is just a question of whether b is a variable in the big O notation.
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.
- SamReidHughes 10y ago> 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.
- DanWaterworth 10y agoI don't know where you got those numbers from.
- SamReidHughes 10y ago> The reason is, the binary tree accesses that a single b-sized access replaces get exponentially more "local." 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.)
- DanWaterworth 10y agoThanks, I see. Are you assuming ephemeral usage of nodes to make that claim?
- SamReidHughes 10y agoI don't know what that means. I'm assuming a random element of the tree is picked, that parent nodes are in a smaller or equal cache level than children, that all but one cache levels are used completely, that each cache level has O(sqrt n) access time, and that there is an upper bound on the ratio between successive cache sizes. 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.
- DanWaterworth 10y agoRight, you're assuming there's one tree being maintained.
- SamReidHughes 10y agoOr any fixed number of them, or any curve where the number is polynomially smaller than the total size...