5 ms·

Thanks, I see. Are you assuming ephemeral usage of nodes to make that claim?

• SamReidHughes 10y ago
  I 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 ago
    Right, you're assuming there's one tree being maintained.
    • SamReidHughes 10y ago
      Or any fixed number of them, or any curve where the number is polynomially smaller than the total size...